We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Binary Tree Coloring Game

Difficulty: Medium

Problem Description

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. The first player colors a node with value x red, and the second player colors a node with value y blue. The players take turns coloring uncolored neighbors of their respective colored nodes. The game ends when both players cannot make a move, 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.

Key Insights

  • The objective is to find a node y that allows the second player to outnumber the first player after all possible moves.
  • The game involves strategic selection of nodes based on the tree structure and the initial choice of x.
  • The size of the subtrees can determine the number of nodes each player can color, influencing the outcome.

Space and Time Complexity

Time Complexity: O(n) - We need to traverse the entire tree to count nodes in subtrees. Space Complexity: O(h) - The space used by the recursion stack, where h is the height of the tree.

Solution

To solve the problem, we can utilize Depth-First Search (DFS) to traverse the binary tree. We first locate the node with value x and then calculate the sizes of its left and right subtrees. The second player must choose a node that maximizes their potential to color more nodes than the first player. The critical observation is that if the size of either the left or right subtree is greater than half of the total nodes, the second player can ensure victory by choosing an appropriate node from that subtree.

Code Solutions

def btreeGameWinningMove(root, n, x):
    # Helper function to count the size of the subtree
    def count_nodes(node):
        if not node:
            return 0
        return 1 + count_nodes(node.left) + count_nodes(node.right)

    # Find the target node x
    def find_node(node, x):
        if not node:
            return None
        if node.val == x:
            return node
        left = find_node(node.left, x)
        if left:
            return left
        return find_node(node.right, x)

    target_node = find_node(root, x)
    left_size = count_nodes(target_node.left)
    right_size = count_nodes(target_node.right)
    
    # The size of the remaining nodes that can be colored by player 2
    remaining = n - (1 + left_size + right_size)

    # Player 2 wins if they can color more than half of the nodes
    return max(left_size, right_size, remaining) > n // 2
← Back to All Questions