LeetCode 1145 - Binary Tree Coloring Game

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

The problem is a two-player game played on a binary tree, where each player colors nodes starting from an initial chosen node. Player 1 picks a node x and colors it red, while Player 2 picks a different node y and colors it blue. Players then alternate turns, coloring an uncolored neighbor (parent, left child, or right child) of a node they already own. The game ends when neither player can make a move, and the winner is the player who has colored more nodes.

As the second player, the goal is to determine if there exists a node y such that choosing it guarantees a win. The input consists of the tree root, the total number of nodes n (odd, unique values from 1 to n), and the first player's choice x. The output is a boolean: true if the second player can guarantee a win, false otherwise.

Key constraints include the small maximum n of 100, which allows depth-first searches without worrying about stack overflow. The odd n ensures that ties are impossible, so winning is strictly about controlling more than half the nodes. Important edge cases include a very small tree (e.g., n=3) or when the chosen node x is the root, which splits the tree in ways that affect Player 2's strategy.

The critical insight is that the second player cannot always win by brute-force simulation; instead, the game outcome depends on the sizes of the three distinct regions formed when Player 1 colors node x: the left subtree of x, the right subtree of x, and the rest of the tree (parent side). If the second player can control a region larger than half of n, they can guarantee victory.

Approaches

The brute-force approach is to simulate all possible sequences of moves for both players starting from every possible choice of y. This guarantees correctness but is prohibitively slow because the number of game states grows exponentially with n. Specifically, for each move, multiple options exist for coloring neighbors, and the game can continue up to n turns, yielding a state space of O(3^n) in the worst case.

The optimal approach leverages the structural insight: instead of simulating the game, we compute the sizes of the three regions created by Player 1's initial choice x. These regions are the left subtree of x, the right subtree of x, and the "parent side" (all nodes not in the subtree rooted at x). Player 2 can then pick a node in the largest of these three regions. If this region has more than n / 2 nodes, Player 2 can control a majority and guarantee victory. This reduces the problem to a single traversal of the tree to compute subtree sizes, giving linear time complexity.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(3^n)	O(n)	Simulate every possible move sequence for both players
Optimal	O(n)	O(n)	Compute subtree sizes via DFS, then check largest region relative to n/2

Algorithm Walkthrough

Perform a DFS traversal starting from the root to locate node x. While traversing, compute the size of each subtree, returning the size of the subtree rooted at each node.
Once node x is located, record the size of its left subtree and right subtree.
Compute the size of the "parent side" region by subtracting the size of node x's subtree (including x) from the total number of nodes n.
Determine the maximum size among the left, right, and parent regions.
If the maximum size is strictly greater than n / 2, Player 2 can choose a node in that region to control more than half of the nodes and guarantee a win. Otherwise, Player 2 cannot guarantee victory.

Why it works: The game mechanics restrict players to coloring connected components starting from their initial node. By splitting the tree at node x, the three resulting regions are isolated with respect to Player 1. Controlling the largest region ensures Player 2 can eventually color more nodes than Player 1. Since n is odd, having strictly more than half the nodes guarantees victory.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from typing import Optional

class Solution:
    def btreeGameWinningMove(self, root: Optional['TreeNode'], n: int, x: int) -> bool:
        self.left_size = 0
        self.right_size = 0
        
        def count_subtree(node: Optional['TreeNode']) -> int:
            if not node:
                return 0
            left = count_subtree(node.left)
            right = count_subtree(node.right)
            if node.val == x:
                self.left_size = left
                self.right_size = right
            return left + right + 1
        
        count_subtree(root)
        parent_size = n - (self.left_size + self.right_size + 1)
        max_region = max(self.left_size, self.right_size, parent_size)
        return max_region > n // 2

The Python solution defines a DFS helper count_subtree that recursively counts the nodes in each subtree. When the target node x is encountered, the sizes of its left and right subtrees are recorded. The size of the remaining "parent side" is computed from the total node count minus the size of x's entire subtree. Finally, the maximum of these three regions is compared to n // 2 to determine if Player 2 can guarantee a win.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func btreeGameWinningMove(root *TreeNode, n int, x int) bool {
    var leftSize, rightSize int
    
    var countSubtree func(node *TreeNode) int
    countSubtree = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        left := countSubtree(node.Left)
        right := countSubtree(node.Right)
        if node.Val == x {
            leftSize = left
            rightSize = right
        }
        return left + right + 1
    }
    
    countSubtree(root)
    parentSize := n - (leftSize + rightSize + 1)
    maxRegion := leftSize
    if rightSize > maxRegion {
        maxRegion = rightSize
    }
    if parentSize > maxRegion {
        maxRegion = parentSize
    }
    
    return maxRegion > n/2
}

The Go solution mirrors the Python approach. It uses a recursive closure countSubtree to calculate subtree sizes. The nil check corresponds to Python’s None. Maximum region calculation is done manually using conditional comparisons, and the result is returned based on whether Player 2 can control more than half of the nodes.

Worked Examples

Example 1:

Input: root = [1,2,3,4,5,6,7,8,9,10,11], n = 11, x = 3

Perform DFS and find node 3.
Left subtree size of node 3 is 6 (nodes 6,7,8,9,10,11), right subtree size is 0.
Parent side size is n - (left + right + 1) = 11 - (6+0+1) = 4.
Maximum region size is 6.
Since 6 > 11 // 2 = 5, return true.

Example 2:

Input: root = [1,2,3], n = 3, x = 1

Node 1 has left size 1 and right size 1.
Parent side size = 3 - (1+1+1) = 0.
Maximum region size = 1.
Since 1 <= 3 // 2 = 1, return false.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single DFS traversal to compute subtree sizes and locate node x
Space	O(n)	Recursion stack in worst case for skewed tree, or O(log n) for balanced tree

The linear time complexity comes from visiting each node exactly once during DFS. Space complexity depends on the height of the tree; in the worst case of a skewed tree, recursion stack reaches O(n).

Test Cases

# Provided examples
assert Solution().btreeGameWinningMove(TreeNode(1, TreeNode(2), TreeNode(3)), 3, 1) == False  # small tree
assert Solution().btreeGameWinningMove(TreeNode(1,
    TreeNode(2, TreeNode(4), TreeNode(5)),
    TreeNode(3, TreeNode(6), TreeNode(7))
), 7, 3) == True  # larger tree

# Edge cases
assert Solution().btreeGameWinningMove(TreeNode(1), 1, 1) == False  # single node
assert Solution().btreeGameWinningMove(TreeNode(1, TreeNode(