Watch 10 video solutions for Binary Tree Coloring Game, a medium level problem involving Tree, Depth-First Search, Binary Tree. This walkthrough by Pepcoding has 5,668 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Example 1:
Input: root = [1,2,3,4,5,6,7,8,9,10,11], n = 11, x = 3 Output: true Explanation: The second player can choose the node with value 2.
Example 2:
Input: root = [1,2,3], n = 3, x = 1 Output: false
Constraints:
n.1 <= x <= n <= 100n is odd.Problem Overview: You are given a binary tree with n nodes. Player 1 colors a node x. Player 2 then chooses another node. Each player expands to adjacent nodes (parent or children). The goal is to control more than half of the nodes. The question: can the second player pick a node that guarantees a win?
Approach 1: Analyze Subtree Sizes (O(n) time, O(h) space)
The key observation is that the first player's move splits the tree into three independent regions: the left subtree of x, the right subtree of x, and the remaining part of the tree above x (the parent side). If the second player picks a node in the largest of these regions, they can lock Player 1 out of it and claim all nodes there. Use a depth-first search to locate node x and compute the size of its left and right subtrees. The parent region size is n - (left + right + 1). If any of these three regions has more than n/2 nodes, Player 2 can start there and guarantee control of that entire section. This approach works because movement is restricted to adjacent nodes in the binary tree, preventing Player 1 from crossing into the chosen region once Player 2 occupies its root.
Approach 2: Use a Queue for Level Order Traversal (O(n) time, O(n) space)
Another way to reason about the regions is with a queue-based tree traversal. First perform a level order traversal to locate node x and record parent relationships if needed. Once found, run BFS traversals starting from the left child, right child, and parent side (excluding x) to count how many nodes belong to each region. Each BFS expands through valid neighbors while avoiding revisiting x. After counting, compare the sizes of the three partitions with n/2. If any region exceeds half the nodes, Player 2 can start there and isolate Player 1. This method is easier to reason about when thinking in terms of reachable areas but uses more memory due to the queue and visited tracking.
Recommended for interviews: The subtree size analysis using DFS is the expected solution. It runs in linear time, uses minimal memory proportional to tree height, and demonstrates strong understanding of tree partitioning. The BFS region-counting approach still works but is less elegant and usually unnecessary once you recognize how the first move divides the tree.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Analyze Subtree Sizes (DFS) | O(n) | O(h) | Best general solution. Efficient when you can compute subtree sizes during a single DFS traversal. |
| Queue-Based Level Order Traversal | O(n) | O(n) | Useful when reasoning about reachable regions using BFS or when parent relationships are explicitly tracked. |