How do you solve Binary Tree Coloring Game on LeetCode?

Binary Tree Coloring Game (LeetCode #1145) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Player 2's choice of y should be adjacent to x to maximize their control over the game.

What is the brute force solution for Binary Tree Coloring Game?

The brute force approach for Binary Tree Coloring Game is Brute Force, with O(n²) time complexity and O(1) space complexity. In the brute force approach, we will simulate the game by trying every possible move for player 2 after player 1 colors their chosen node. We will check if player 2 can always ensure more nodes colored than player 1. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Binary Tree Coloring Game?

Binary Tree Coloring Game uses the following concepts: Tree, Depth-First Search, Binary Tree. The recommended patterns to study are: Tree Traversal, Depth-First Search.

What are the interview tips for Binary Tree Coloring Game?

Clarify how the game works and what winning means before diving into the solution. Think about edge cases, such as very small trees or trees where x is a leaf. Practice explaining your thought process clearly as you work through the problem.

What are common mistakes when solving Binary Tree Coloring Game?

Failing to consider the parent node when calculating potential moves. Overlooking the fact that player 2 can win by simply having more nodes than player 1.

#1145

Binary Tree Coloring Game

Medium

TreeDepth-First SearchBinary TreeTree TraversalDepth-First Search

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

In the optimal solution, we can directly calculate the sizes of the subtrees formed by the neighbors of x. This allows us to determine if player 2 can secure more nodes without simulating the entire game.

⚙️

Algorithm

5 steps

1Step 1: Find the node x in the tree.
2Step 2: Count the number of nodes in the left and right subtrees of x.
3Step 3: Calculate the number of nodes that player 2 can color from the parent node.
4Step 4: Determine the maximum of the three counts (left, right, parent).
5Step 5: If the maximum count is greater than n/2, return true; otherwise, return false.

solution.py30 lines

1class TreeNode:
2    def __init__(self, val=0, left=None, right=None):
3        self.val = val
4        self.left = left
5        self.right = right
6
7class Solution:
8    def btreeGameWinningMove(self, root: TreeNode, n: int, x: int) -> bool:
9        def count_nodes(node):
10            if not node:
11                return 0
12            return 1 + count_nodes(node.left) + count_nodes(node.right)
13
14        x_node = self.find_node(root, x)
15        left_count = count_nodes(x_node.left)
16        right_count = count_nodes(x_node.right)
17        parent_count = n - (left_count + right_count + 1)
18
19        max_count = max(left_count, right_count, parent_count)
20        return max_count > n // 2
21
22    def find_node(self, node, x):
23        if not node:
24            return None
25        if node.val == x:
26            return node
27        left = self.find_node(node.left, x)
28        if left:
29            return left
30        return self.find_node(node.right, x)

ℹ

Complexity note: The time complexity is O(n) because we only traverse the tree a few times to find the node and count the subtrees, which is efficient compared to the brute force method.

1Player 2's choice of y should be adjacent to x to maximize their control over the game.
2Counting the sizes of the subtrees allows for a quick determination of potential winning moves.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.