Binary Tree Coloring Game: Counting Subtree Sizes

You are given the root of a binary tree with n nodes, each uniquely valued from 1 to n. Two players take turns coloring nodes. Player 1 colors node x red on the first move. Player 2 then colors any uncolored node adjacent to one of their colored nodes on each turn, and so does player 1. The player who colors more nodes wins. Given n and x, determine if player 2 can guarantee a win regardless of how player 1 plays.

This is LeetCode 1145: Binary Tree Coloring Game, and it is one of the best problems for learning how tree structure creates natural partitions that you can count and compare.

Why this problem matters

At first glance, this looks like a complex game theory problem. Two players competing on a tree, alternating moves, coloring nodes. It feels like you might need minimax or dynamic programming on game states. But the tree structure makes the problem dramatically simpler than it appears. Once player 1 picks node x, the tree splits into exactly three regions, and the entire game reduces to counting sizes. This kind of structural insight, where the shape of the data structure collapses the problem into something trivial, is exactly what interviewers want to see.

The pattern of counting subtree sizes and comparing them to a threshold shows up across tree problems. It connects to problems about removing edges, finding centroids, and balancing partitions.

The key insight

When player 1 colors node x, that node divides the tree into exactly three regions:

1. The left subtree of x
2. The right subtree of x
3. Everything else (the "parent side," meaning all nodes reachable through x's parent)

Player 2's optimal strategy is simple: pick the neighbor of x that leads to the largest of these three regions. Once player 2 blocks that edge, they claim the entire region. Player 1 gets the rest. Player 2 wins if and only if the largest region contains more than half the total nodes.

So the algorithm is:

1. Find node x in the tree.
2. Count the sizes of its left and right subtrees (call them left and right).
3. Compute the parent side as n - 1 - left - right.
4. Return true if max(left, right, n - 1 - left - right) is greater than n / 2.

The solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def btree_game_winning_move(root: TreeNode, n: int, x: int) -> bool:
    left_count = 0
    right_count = 0

    def count(node: TreeNode) -> int:
        nonlocal left_count, right_count
        if not node:
            return 0
        l = count(node.left)
        r = count(node.right)
        if node.val == x:
            left_count = l
            right_count = r
        return 1 + l + r

    count(root)
    parent_count = n - 1 - left_count - right_count
    return max(left_count, right_count, parent_count) > n // 2

Let's walk through what each piece does.

The count function is a standard recursive subtree size calculation. It returns the total number of nodes in the subtree rooted at node. For every node, we recursively count its left and right children, then return 1 + l + r.

The key addition is the check if node.val == x. When we find the node that player 1 picked, we save its left and right subtree sizes into the outer variables left_count and right_count. This is the only extra work we do beyond a normal tree traversal.

After the traversal finishes, we compute the parent side. Since the total tree has n nodes, and we know node x itself takes 1 node, its left subtree takes left_count, and its right subtree takes right_count, the parent side is just n - 1 - left_count - right_count.

Finally, we check if the largest of the three regions exceeds half the total. If it does, player 2 can win by picking the neighbor that leads into that region. Integer division with n // 2 works here because ties (where both players get exactly n / 2 nodes) are impossible when n is odd, and if n is even a tie means player 2 does not win.

Visual walkthrough

Let's trace through the example tree with n = 11 and x = 3. Watch how the three regions form around the node player 1 picks, and how player 2 evaluates each one.

The parent side dominates with 8 nodes, well over half of 11. Player 2 picks node 1 (the parent of node 3) and claims the entire upper portion of the tree. Player 1 is stuck with only 3 nodes: node 3 itself plus its two children. The game is not even close.

Complexity analysis

Time is O(n) because we perform a single DFS that visits every node exactly once. At each node we do O(1) work: recursing into children, checking if the node matches x, and returning a count.

Space is O(n) due to the recursion stack. In the worst case (a completely skewed tree), the recursion depth equals n. For a balanced tree, the stack depth is O(log n), but the worst case is linear.

The building blocks

1. Counting subtree sizes with DFS

The recursive pattern that returns the size of a subtree rooted at a given node:

def count(node):
    if not node:
        return 0
    return 1 + count(node.left) + count(node.right)

This is one of the most fundamental tree operations. You see it in problems about balanced trees, tree diameter, subtree sums, and anywhere you need to know "how many nodes are below this point." The pattern is always the same: base case returns 0, recursive case returns 1 plus the sum of children.

2. Partitioning a tree by removing a node

When you remove a node from a binary tree, it creates up to three disconnected components. Computing the size of each component without actually modifying the tree:

left_size = count(node.left)
right_size = count(node.right)
parent_size = n - 1 - left_size - right_size

This "complementary counting" trick avoids traversing the parent side separately. You already know the total (n), and you know the parts you can directly measure (1 + left_size + right_size). The remainder is the parent side. This pattern appears in problems about removing edges from trees, finding centroids, and partitioning trees into balanced components.

Edge cases

• Node x is the root: the parent side has size 0. Player 2 can only pick a child, so they get whichever subtree is larger. Player 2 wins if max(left, right) > n / 2.
• Node x is a leaf: both subtree sizes are 0. The parent side is n - 1. Player 2 picks the parent and claims n - 1 nodes. Player 2 always wins (since n >= 2 in the constraints).
• Perfectly balanced tree, x is the root: left and right subtrees each have (n - 1) / 2 nodes. Neither exceeds n / 2, so player 2 cannot win. This is the hardest case for player 2.
• n = 1: only one node exists. Player 1 takes it, and there is nothing for player 2 to pick. According to constraints n >= 1, but player 2 cannot win when n = 1.

From understanding to recall

The insight behind this problem is elegant: a game that looks adversarial reduces to counting three numbers and checking a maximum. Once you see that removing node x partitions the tree into three regions, the solution writes itself. But getting to that insight under pressure requires having seen the pattern before.

The subtree counting pattern and the complementary counting trick are building blocks that appear in many tree problems. If you have drilled them independently, you recognize them immediately when they show up together here. You do not waste time rediscovering the approach from scratch.

Spaced repetition locks in both the structural insight (three regions) and the implementation details (single-pass DFS, saving subtree sizes at the target node, computing the complement). After a few review cycles, you see "player picks a node on a tree" and immediately think "partition into regions, count sizes, compare to threshold." The pattern becomes automatic.

Related posts

• Diameter of Binary Tree - Another problem where a single DFS computes subtree properties and combines them at each node
• Binary Tree Maximum Path Sum - Uses the same "track a global answer while returning local info up the tree" pattern
• Count Complete Tree Nodes - Efficient subtree counting with structural properties of the tree

CodeBricks breaks Binary Tree Coloring Game into its subtree counting and tree partitioning building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a tree partitioning problem shows up in your interview, you do not think about it. You just write it.