MediumTreeDepth-First SearchBinary TreeUpdated Sep 2026

1145. Binary Tree Coloring Game

Asked at Anduril

Difficulty

Medium

Time

O(n)

Space

O(h)

Pattern

Tree

Companies

1

Problem

Two players color nodes of a binary tree with n nodes (n is odd, every node has a unique value from 1 to n). Player 1 first picks a value x and colors that node red. You are player 2: you pick a different value y and color that node blue.

After that, players take turns, starting with player 1. On your turn you must pick one of your own colored nodes and color an uncolored neighbor of it (its left child, right child, or parent). If you have no such move, you pass. The game ends when both players pass, and whoever colored more nodes wins.

Return true if you can choose some y that guarantees you win, otherwise return false.

Node x cuts the tree into three parts

849210511163player 17The red node x = 3 is already taken by player 18492parent side: 81051116left: 137right: 1Three regions: left subtree (1), right subtree (1), parent side (8)
Player 1 already owns node 3. You can grab one of the three regions next to it, and player 1 can never enter that region.

Constraints

  • ●The tree has exactly n nodes.
  • ●1 <= x <= n <= 100
  • ●n is odd.
  • ●1 <= Node.val <= n
  • ●All node values are unique.

Examples

Example 1
Inputroot = [1,2,3,4,5,6,7,8,9,10,11], n = 11, x = 3
Outputtrue
WhyNode 3 splits the tree into three parts: its left subtree (node 6, size 1), its right subtree (node 7, size 1), and everything above it (8 nodes). If you pick y = 2, you claim the whole upper part of 8 nodes, which is more than half of 11.
Example 2
Inputroot = [1,2,3], n = 3, x = 1
Outputfalse
WhyNode 1 is the root, so the three parts are its left subtree (1 node), right subtree (1 node), and the parent side (0 nodes). The best you can get is 1 node, which is not more than 3 / 2 = 1.

Asked At

1 companies
CompanyDifficulty
AndurilMediumView all Anduril questions →

How to Think About It

1

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).

2

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.

3

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.

4

Find x and the subtree sizes in one DFS that returns subtree sizes and records the child sizes when it reaches x.

5

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).

Count the three regions, take the biggest

DFS: subtree sizesrecord left, right at xparentSide = n - left - right - 1max(left, right, parentSide) > n // 2One DFS gives both child sizes; the parent side iswhatever is left over.left = 1, right = 1parentSide = 11 - 1 - 1 - 1 = 8max(1, 1, 8) = 8 > 5return true
The answer is true exactly when the largest region has more than n / 2 nodes.
ComplexityTime O(n)Space O(h)One DFS visits every node once; h is the tree height, the depth of the recursion stack.

What Trips People Up in Real Interviews

1

Trying to simulate the game. The whole game is decided by one choice of region.

2

Forgetting the parent-side region — often it is the largest one.

3

Using >= instead of >: with n odd you need strictly more than half.

4

Recounting subtree sizes separately for x.left and x.right after finding x — one DFS is enough.

Solution Code

O(n) time
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 // 2

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O(n) time and O(h) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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.