Binary Tree Coloring Game - Leetcode Solution

Problem Statement:

Two players play a turn-based game on a binary tree. We are given the root of this binary tree, and the number of nodes n in the tree. n is odd, and each node has a distinct value from 1 to n.

Initially, the first player names a value x with 1 <= x <= n, and the second player names a value y with 1 <= y <= n and y != x. The first player colors the node with value x red, and the second player colors the node with value y blue.

Then, the players take turns starting with the first player. In each turn, that player chooses a node of their color (red if player 1, blue if player 2) and colors an uncolored neighbor of the chosen node (either the left child, right child, or parent of the chosen node.)

If (and only if) a player cannot choose such a node in this way, they must pass their turn. If both players pass their turn, the game ends, and the winner is the player that colored more nodes.

You are the second player. If it is possible to choose such a y to ensure you win the game, return true. If it is not possible, return false.

Solution:

To solve this problem, we need to first determine the possible winning strategies for the second player. The goal of the second player is to color more nodes than the first player; hence, the second player would want to choose a node that ensures that they can color more nodes than the first player.

We can start by calculating the sizes of the left and right subtrees for the node colored with x. Let l be the size of the left subtree and r be the size of the right subtree. Without loss of generality, we assume that l <= r.

First, the second player can choose the parent of the node colored with x. This ensures that the first player can only color one subtree, which means that the maximum number of nodes that the first player can color is max(l, r-1). Hence, the second player can color the other subtree, which has size min(l, r-1) and can always ensure that they color more nodes than the first player.

If the second player cannot choose the parent of the node colored with x, they can choose the larger subtree. If l > r/2, then the second player can color the entire left subtree, which has size l, while the first player can color at most r/2 nodes in the right subtree. Hence, the second player can ensure that they color more nodes than the first player.

Similarly, if r > l/2, then the second player can color the entire right subtree, which has size r, while the first player can color at most l/2 nodes in the left subtree. Hence, the second player can ensure that they color more nodes than the first player.

If none of the above strategies work, then the second player cannot win the game. Hence, we return false.

Here is the Python code to implement the above algorithm:

class Solution:
    def btreeGameWinningMove(self, root: TreeNode, n: int, x: int) -> bool:
        def count_nodes(node):
            if node is None:
                return 0
            return count_nodes(node.left) + count_nodes(node.right) + 1
        
        def find_node(node, value):
            if node is None:
                return None
            if node.val == value:
                return node
            left = find_node(node.left, value)
            if left is not None:
                return left
            right = find_node(node.right, value)
            if right is not None:
                return right
            return None
        
        def count_subtree(node):
            if node is None:
                return 0
            return count_nodes(node.left) + count_nodes(node.right) + 1
        
        def can_win_on_parent(node):
            p = find_node(root, x)
            return p != node and n - count_subtree(p) < count_subtree(p)
        
        def can_win_on_larger_subtree(node):
            l = count_nodes(node.left)
            r = count_nodes(node.right)
            if l > r//2:
                return l > n - l
            if r > l//2:
                return r > n - r
            return False
        
        x_node = find_node(root, x)
        l = count_nodes(x_node.left)
        r = count_nodes(x_node.right)
        if can_win_on_parent(x_node):
            return True
        if can_win_on_larger_subtree(x_node.left) or can_win_on_larger_subtree(x_node.right):
            return True
        return False

The time complexity of the algorithm is O(n), where n is the number of nodes in the binary tree.

1