Binary Tree Coloring Game
Asked at Anduril
Problem
Binary Tree Coloring Game has two players color nodes of a tree with n (odd) nodes: player one has already colored node x, and you choose one node y. Players then alternately grow their colored region into adjacent uncolored nodes. Can you choose y so that you end up with more nodes? The game reduces to counting subtree sizes.
Asked At
| Company | Difficulty | |
|---|---|---|
| Anduril | Medium | View all Anduril questions → |
How to Think About It
Node x splits the rest of the tree into at most three regions: its left subtree, its right subtree, and everything above it (through its parent).
Key insight: if you pick y adjacent to x in one of those regions, player one can never enter that region — you get all of it. And player one can never take more than the rest.
So compute left = size(x.left), right = size(x.right), and parentSide = n - left - right - 1. You win iff the largest of the three is more than n / 2.
Find x and the subtree sizes in one DFS that returns subtree sizes and records the child sizes when it reaches x.
Walkthrough for root = [1,2,3,4,5,6,7,8,9,10,11], n = 11, x = 3: node 3 has one-node subtrees on each side (6 and 7), so left = 1, right = 1, and parentSide = 11 - 1 - 1 - 1 = 8. Picking y = 1 claims 8 nodes, which is more than 5 -> true.
Optimal Approach
Step 1: DFS returning the size of each subtree; when the current node has value x, record left and right sizes.
Step 2: parentSide = n - left - right - 1.
Step 3: Return max(left, right, parentSide) > n // 2.
Time: O(n). Space: O(h).
What Trips People Up in Real Interviews
Trying to simulate the game. The whole game is decided by one choice of region.
Forgetting the parent-side region — often it is the largest one.
Using >= instead of >: with n odd you need strictly more than half.
Recounting subtree sizes separately for x.left and x.right after finding x — one DFS is enough.
Solution Code
def btreeGameWinningMove(root, n, x):
sizes = {}
def count(node):
if not node:
return 0
l = count(node.left)
r = count(node.right)
if node.val == x:
sizes['l'], sizes['r'] = l, r
return l + r + 1
count(root)
l, r = sizes['l'], sizes['r']
parent_side = n - l - r - 1
return max(l, r, parent_side) > n // 2Frequently Asked Questions
What is the Binary Tree Coloring Game problem?
Binary Tree Coloring Game has two players color nodes of a tree with `n` (odd) nodes: player one has already colored node `x`, and you choose one node `y`. Players then alternately grow their colored region into adjacent uncolored nodes. Can you choose `y` so that you end up with more nodes? The game reduces to counting subtree sizes.
How do you solve Binary Tree Coloring Game?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Binary Tree Coloring Game?
Binary Tree Coloring Game is asked at Anduril. It is a medium difficulty problem.
What are common mistakes on Binary Tree Coloring Game?
- Trying to simulate the game. The whole game is decided by one choice of region.
- Forgetting the parent-side region — often it is the largest one.
- Using `>=` instead of `>`: with `n` odd you need strictly more than half.
- Recounting subtree sizes separately for `x.left` and `x.right` after finding `x` — one DFS is enough.