Binary Tree Coloring Game

medium binary tree dfs game theory

Problem

Two players play on a binary tree of n nodes (n is odd) whose values are 1..n. Player 1 colors node x red. Player 2 picks a different node y and colors it blue. Then players alternate: each turn you pick an uncolored node adjacent to one of your colored nodes and color it your color. The player with more colored nodes at the end wins. Given the tree and x, return true if Player 2 can choose y to guarantee a win.

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

Outputtrue

Node 3 splits the tree into three regions: parent side (7 nodes), left child of 3 (2 nodes), right child of 3 (1 node). Player 2 picks node 2 to grab the 7-node parent side, which exceeds 11/2.

tree (level-order, comma-separated, "null" for empty)

x (value)

def btree_game_winning_move(root, n, x):
    left = right = 0
    def count(node):
        nonlocal left, right
        if not node:
            return 0
        l = count(node.left)
        r = count(node.right)
        if node.val == x:
            left, right = l, r
        return l + r + 1
    count(root)
    parent = n - left - right - 1
    return max(left, right, parent) > n // 2

function btreeGameWinningMove(root, n, x) {
  let left = 0, right = 0;
  function count(node) {
    if (!node) return 0;
    const l = count(node.left);
    const r = count(node.right);
    if (node.val === x) { left = l; right = r; }
    return l + r + 1;
  }
  count(root);
  const parent = n - left - right - 1;
  return Math.max(left, right, parent) > Math.floor(n / 2);
}

class Solution {
    int left = 0, right = 0, x;
    public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
        this.x = x;
        count(root);
        int parent = n - left - right - 1;
        return Math.max(parent, Math.max(left, right)) > n / 2;
    }
    int count(TreeNode node) {
        if (node == null) return 0;
        int l = count(node.left);
        int r = count(node.right);
        if (node.val == x) { left = l; right = r; }
        return l + r + 1;
    }
}

class Solution {
    int left = 0, right = 0, x;
    int count(TreeNode* node) {
        if (!node) return 0;
        int l = count(node->left);
        int r = count(node->right);
        if (node->val == x) { left = l; right = r; }
        return l + r + 1;
    }
public:
    bool btreeGameWinningMove(TreeNode* root, int n, int x) {
        this->x = x;
        count(root);
        int parent = n - left - right - 1;
        return max(parent, max(left, right)) > n / 2;
    }
};

Explanation

The key realization is that Player 1's chosen node x splits the rest of the tree into three regions, and Player 2 just needs to grab the biggest one.

Those three regions are: the left subtree of x, the right subtree of x, and everything else (the parent side, above x). Whichever region Player 2 starts in, Player 1 is walled off from it, so Player 2 claims that whole region.

A single DFS count returns subtree sizes. When it reaches x, it records left and right as the sizes of x's two children's subtrees. The parent side is then just n - left - right - 1 (the whole tree minus both child regions minus x itself).

Player 2 wins if the largest of these three regions is more than half the nodes, i.e. max(left, right, parent) > n // 2.

Example: n = 11, x = 3 gives left = 2, right = 1, parent = 7. Since 7 > 5, Player 2 picks the parent side and wins, so the answer is true.

Time: O(n) Space: O(h)