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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Binary Tree Coloring Game

Number: 1248

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given a binary tree with an odd number of nodes where each node has a unique value from 1 to n, two players take turns coloring nodes. The first player chooses a node with value x, and the second player then picks a different node with value y. In subsequent turns, each player colors an uncolored neighbor (parent, left child, or right child) of a previously colored node of their own color. The game ends when both players can no longer make a move. The goal is to determine if the second player can choose a node y such that they can guarantee a win by eventually coloring more nodes than the first player.

Key Insights

  • The node chosen by the first player (with value x) partitions the tree into three regions: the left subtree of x, the right subtree of x, and the "parent region" (all nodes not in the left or right subtree of x).
  • The best move for the second player is to choose a node from the region that has the maximum number of nodes.
  • If any one of these regions contains more than half of the nodes (i.e. > n/2), then the second player can secure a win.

Space and Time Complexity

Time Complexity: O(n) – We perform a DFS traversal to count nodes in the subtrees. Space Complexity: O(n) – In the worst case, the recursion stack may reach O(n) for a skewed tree.

Solution

We solve the problem by performing a DFS to count the number of nodes in the left and right subtrees of the node with value x. Once we have these counts, we determine the number of nodes in the remaining region, which is n - (left_count + right_count + 1). The second player can guarantee victory if the maximum count among these three regions is greater than half the total nodes (n/2). We use DFS because it allows us to count nodes in each subtree efficiently.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def btreeGameWinningMove(self, root: TreeNode, n: int, x: int) -> bool:
        self.left_count = 0  # to store count of left subtree of x
        self.right_count = 0  # to store count of right subtree of x

        # DFS to count nodes in each subtree, and capture counts for node x.
        def count_nodes(node):
            if not node:
                return 0
            left = count_nodes(node.left)
            right = count_nodes(node.right)
            # If this node is the one colored by first player (x),
            # record its left and right subtree sizes.
            if node.val == x:
                self.left_count = left
                self.right_count = right
            return 1 + left + right

        # Start DFS from the root.
        count_nodes(root)
        
        parent_count = n - (self.left_count + self.right_count + 1)
        # The second player wins if one of the regions has more than n//2 nodes.
        max_region = max(self.left_count, self.right_count, parent_count)
        return max_region > n // 2

# Example usage:
# root = TreeNode(1, TreeNode(2), TreeNode(3)) ...
# sol = Solution()
# result = sol.btreeGameWinningMove(root, n, x)
← Back to All Questions