Problem Description

The Binary Tree Coloring Game is a two-player game played on a binary tree with n nodes, each uniquely valued from 1 to n. The game works as follows:

• Player 1 colors a node with value x red.
• Player 2 then colors a different node blue.
• Players alternate turns, each coloring an uncolored node that is adjacent (parent or child) to a node they've already colored.
• The game ends when neither player can make a move.
• The winner is the player who has colored more nodes.

Given the root of the binary tree, the total number of nodes n, and the value x (the node Player 1 colors first), determine if Player 2 can guarantee a win by choosing the right starting node.

Constraints:

• Each node in the tree has a unique value.
• 1 <= n <= 100
• There is only one valid solution for each input.

Thought Process

The first instinct might be to simulate the entire coloring process, trying all possibilities for Player 2. However, with up to 100 nodes, simulating every move would be inefficient and complex.

Instead, let's analyze the structure of the tree after Player 1 colors node x:

• Player 1 "owns" the node x and can only expand from it.
• Player 2 can choose any node not colored, ideally one that maximizes the number of nodes they can reach before Player 1 does.

1. The left subtree of x
2. The right subtree of x
3. The "rest" of the tree (the part above x, i.e., the parent and its ancestors and their subtrees not containing x)

Solution Approach

To solve the problem efficiently, we use the following steps:

1. Find Node x:
   • Traverse the tree to locate the node with value x.
2. Count Subtree Sizes:
   • For node x, compute the size of its left subtree and right subtree.
   • The "parent side" (nodes not in x's subtree) is n - (left + right + 1).
3. Decide Winning Move:
   • Player 2 can guarantee a win if they can color a node in the largest region (left, right, or parent side) that contains more than n // 2 nodes.

We use a recursive function to count subtree sizes, and a simple check to determine if Player 2 can win.

Example Walkthrough

Example:
Suppose the tree is:

         1
        / \
       2   3
      / \
     4   5
    

• n = 5, x = 2
• Player 1 colors node 2.
• Left subtree of 2: node 4 (size 1).
• Right subtree of 2: node 5 (size 1).
• Parent side: nodes 1 and 3 (size 2).

Time and Space Complexity

Brute-force approach: Simulating all possible coloring moves is exponential due to the branching factor at each step.

Optimized approach:

• Finding node x and counting subtree sizes is O(n) (each node is visited once).
• Space complexity is O(h), where h is the height of the tree (for recursion stack).

Summary

The Binary Tree Coloring Game can be solved by analyzing how the tree is partitioned by Player 1's initial move. By counting the sizes of the left, right, and parent regions around node x, we can determine if Player 2 can guarantee a win by claiming the largest region. This approach avoids brute-force simulation and leverages tree properties for an elegant and efficient solution.

Code Implementation

# 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

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

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

        count(root)
        parent_side = n - (self.left_count + self.right_count + 1)
        max_region = max(self.left_count, self.right_count, parent_side)
        return max_region > n // 2
      

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int left_count = 0, right_count = 0;
    int count(TreeNode* node, int x) {
        if (!node) return 0;
        int left = count(node->left, x);
        int right = count(node->right, x);
        if (node->val == x) {
            left_count = left;
            right_count = right;
        }
        return left + right + 1;
    }
    bool btreeGameWinningMove(TreeNode* root, int n, int x) {
        count(root, x);
        int parent_side = n - (left_count + right_count + 1);
        int max_region = std::max({left_count, right_count, parent_side});
        return max_region > n / 2;
    }
};
      

// Definition for a binary tree node.
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) {
        count(root, x);
        int parentSide = n - (leftCount + rightCount + 1);
        int maxRegion = Math.max(Math.max(leftCount, rightCount), parentSide);
        return maxRegion > n / 2;
    }
    private int count(TreeNode node, int x) {
        if (node == null) return 0;
        int left = count(node.left, x);
        int right = count(node.right, x);
        if (node.val == x) {
            leftCount = left;
            rightCount = right;
        }
        return left + right + 1;
    }
}
      

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} n
 * @param {number} x
 * @return {boolean}
 */
var btreeGameWinningMove = function(root, n, x) {
    let leftCount = 0, rightCount = 0;
    function count(node) {
        if (!node) return 0;
        let left = count(node.left);
        let right = count(node.right);
        if (node.val === x) {
            leftCount = left;
            rightCount = right;
        }
        return left + right + 1;
    }
    count(root);
    let parentSide = n - (leftCount + rightCount + 1);
    let maxRegion = Math.max(leftCount, rightCount, parentSide);
    return maxRegion > Math.floor(n / 2);
};