Binary Tree Coloring Game - Solution & Explanation
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.
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:
- The number of nodes in the tree is
n. 1 <= x <= n <= 100nis odd.- 1 <= Node.val <= n
- All the values of the tree are unique.
Approach Overview
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 1: Approach 1: Analyze Subtree Sizes
The primary strategy is to maximize control over the number of nodes by the second player. Once Player 1 selects node x, the tree can be divided into three parts: the left subtree of x, the right subtree of x, and the rest of the tree excluding these subtrees. The second player should choose a node such that it controls more than half of the total nodes — this can be achieved if they choose a node from these subtrees which has the largest number of nodes. By comparing the sizes of these parts, the player can determine if it's possible to control more nodes than the opponent.
This solution defines a count_nodes method to calculate the size of each subtree. We keep track of the left and right subtree sizes of node x.
We then compute the size of the rest of the tree that excludes the subtree of x. The second player can win if the maximum size of one of these three regions is greater than half of n.
Code
Python
JavaScript
Complexity
Time Complexity: O(n), where n is the number of nodes, since we traverse the tree once.
Space Complexity: O(h), where h is the height of the tree due to the recursion stack.
Approach 2: Approach 2: Use a Queue for Level Order Traversal
In this approach, we use level order traversal (BFS) to determine the size of subtrees. This is an iterative approach, where we maintain a counter for each subtree identified by node value x and its parent. By comparing these subtrees' sizes, we verify if Player 2 can gain a majority.
This C++ solution performs a recursive traversal to calculate subtree sizes similarly to the Python solution. We count the number of nodes in the left and right subtrees of node x, and use these counts to determine whether the second player can choose a node to gain the advantage.
Complexity
Time Complexity: O(n), due to the traversal of the binary tree.
Space Complexity: O(h), where h is the maximum depth of the tree.
Approach 3: DFS
First, we use DFS to find the node where player 1's colored point x is located, denoted as node.
Next, we count the number of nodes in the left and right subtrees of node, denoted as l and r respectively, and the number of nodes in the direction of node's parent node is n - l - r - 1. As long as max(l, r, n - l - r - 1) > \frac{n}{2}, player 2 has a winning strategy.
The time complexity is O(n), and the space complexity is O(n). Here, n is the total number of nodes.
Code
Python
Java
C++
Go
TypeScript
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Analyze Subtree Sizes | Time Complexity: O(n), where n is the number of nodes, since we traverse the tree once. |
| Approach 2: Use a Queue for Level Order Traversal | Time Complexity: O(n), due to the traversal of the binary tree. |
| DFS | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Binary tree coloring game || Leetcode • Pepcoding • 5,733 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Binary Tree Coloring Game easy or hard?
Binary Tree Coloring Game Python/Java solution
How to solve Binary Tree Coloring Game in O(n)?
What is the best approach for Binary Tree Coloring Game?
Is Binary Tree Coloring Game asked at Google/Amazon/Meta?
What data structure is used in Binary Tree Coloring Game?
What is the time complexity of Binary Tree Coloring Game?
Ready to solve this problem?
Practice Binary Tree Coloring Game with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor