1145. Binary Tree Coloring Game Solution

The problem

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 <= 100
n is 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.

Python

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

class Solution:
    def btreeGameWinningMove(self, root: TreeNode, n: int, x: int) -> bool:
        self.left_count = 0
        self.right_count = 0

        def count_nodes(node):
            if not node:
                return 0
            left = count_nodes(node.left)
            right = count_nodes(node.right)
            if node.val == x:
                self.left_count = left
                self.right_count = right
            return left + right + 1

        count_nodes(root)
        parent_count = n - (self.left_count + self.right_count + 1)
        winner = max(self.left_count, self.right_count, parent_count)
        return winner > n // 2

JavaScript

function TreeNode(val, left, right) {
  this.val = (val===undefined ? 0 : val)
  this.left = (left===undefined ? null : left)
  this.right = (right===undefined ? null : right)
}

var btreeGameWinningMove = function(root, n, x) {
  let leftCount = 0, rightCount = 0;

  const countNodes = (node) => {
    if (!node) return 0;
    let left = countNodes(node.left);
    let right = countNodes(node.right);
    if (node.val === x) {
      leftCount = left;
      rightCount = right;
    }
    return left + right + 1;
  };

  countNodes(root);
  let parentCount = n - (leftCount + rightCount + 1);
  return Math.max(leftCount, rightCount, parentCount) > n / 2;
};

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.

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.

Try this approach in the editor

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.

Java

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    int leftCount = 0, rightCount = 0;

    public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
        countNodes(root, x);
        int parentCount = n - (leftCount + rightCount + 1);
        return Math.max(Math.max(leftCount, rightCount), parentCount) > n / 2;
    }

    private int countNodes(TreeNode node, int x) {
        if (node == null) return 0;
        int left = countNodes(node.left, x);
        int right = countNodes(node.right, x);
        if (node.val == x) {
            leftCount = left;
            rightCount = right;
        }
        return left + right + 1;
    }
}

C++

#include <iostream>
#include <queue>
using namespace std;

struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    bool btreeGameWinningMove(TreeNode* root, int n, int x) {
        int leftCount = 0, rightCount = 0;

        countNodes(root, x, leftCount, rightCount);
        int parentCount = n - (leftCount + rightCount + 1);
        return max({leftCount, rightCount, parentCount}) > n / 2;
    }

private:
    int countNodes(TreeNode* node, int x, int &leftCount, int &rightCount) {
        if (!node) return 0;
        int left = countNodes(node->left, x, leftCount, rightCount);
        int right = countNodes(node->right, x, leftCount, rightCount);

        if (node->val == x) {
            leftCount = left;
            rightCount = right;
        }

        return left + right + 1;
    }
};

This Java solution replicates the strategy shown in Python using a recursive depth-first search to assess the subtree sizes at node x. The method countNodes calculates sizes, which are used to check if Player 2 can select an advantageous node.

Complexity

Time Complexity: O(n), where n is the node count.
Space Complexity: O(h) for the recursion stack, with h as the height of the tree.

Try this approach in the editor

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.

TypeScript

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function btreeGameWinningMove(root: TreeNode | null, n: number, x: number): boolean {
    const dfs = (root: TreeNode | null): TreeNode | null => {
        if (!root || root.val === x) {
            return root;
        }
        return dfs(root.left) || dfs(root.right);
    };

    const count = (root: TreeNode | null): number => {
        if (!root) {
            return 0;
        }
        return 1 + count(root.left) + count(root.right);
    };

    const node = dfs(root);
    const l = count(node.left);
    const r = count(node.right);
    return Math.max(l, r, n - l - r - 1) > n / 2;
}

/**
 * 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 dfs func(*TreeNode) *TreeNode
	dfs = func(root *TreeNode) *TreeNode {
		if root == nil || root.Val == x {
			return root
		}
		node := dfs(root.Left)
		if node != nil {
			return node
		}
		return dfs(root.Right)
	}

	var count func(*TreeNode) int
	count = func(root *TreeNode) int {
		if root == nil {
			return 0
		}
		return 1 + count(root.Left) + count(root.Right)
	}

	node := dfs(root)
	l, r := count(node.Left), count(node.Right)
	return max(max(l, r), n-l-r-1) > n/2
}

Try this approach in the editor

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. Space Complexity: O(h), where h is the height of the tree due to the recursion stack.
Approach 2: Use a Queue for Level Order Traversal	Time Complexity: O(n), where n is the node count. Space Complexity: O(h) for the recursion stack, with h as the height of the tree.
DFS	–

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.

Frequently asked questions

Is Binary Tree Coloring Game easy or hard?

Binary Tree Coloring Game is considered a medium-level problem. The main challenge is recognizing that the first move divides the tree into three regions and that the second player only needs to control the largest region.

Binary Tree Coloring Game Python/Java solution

Most implementations perform a DFS that returns subtree sizes while tracking the left and right sizes of node x. Python and Java solutions typically store these counts during recursion and then check whether any region exceeds n/2.

How to solve Binary Tree Coloring Game in O(n)?

Run a DFS to locate the node chosen by Player 1 and calculate the sizes of its left and right subtrees. The remaining nodes form the parent-side region. If max(leftSubtree, rightSubtree, parentRegion) is greater than n/2, Player 2 can pick a node in that region and win.

What is the best approach for Binary Tree Coloring Game?

The optimal approach analyzes the three regions created by the first player's chosen node: its left subtree, right subtree, and the remaining parent side. A DFS computes subtree sizes in O(n) time. If any region contains more than n/2 nodes, the second player can start there and guarantee a win.

Is Binary Tree Coloring Game asked at Google/Amazon/Meta?

Binary tree strategy and subtree-size problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that require analyzing subtree sizes or partitioning a tree are common in system and algorithm interviews.

What data structure is used in Binary Tree Coloring Game?

The primary data structure is a binary tree. The optimal algorithm uses depth-first search to compute subtree sizes, while alternative implementations may use a queue for breadth-first traversal.

What is the time complexity of Binary Tree Coloring Game?

The optimal solution runs in O(n) time because each node in the binary tree is visited once during a depth-first traversal to compute subtree sizes. Space complexity is O(h) due to recursion stack usage, where h is the tree height.

Binary Tree Coloring Game solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Analyze Subtree Sizes

Approach 2: Approach 2: Use a Queue for Level Order Traversal

Approach 3: DFS

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Binary Tree Coloring Game solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Analyze Subtree Sizes

Approach 2: Approach 2: Use a Queue for Level Order Traversal

Approach 3: DFS

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems