# Binary Tree Coloring Game
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/binary-tree-coloring-game)
Canonical: https://scaleengineer.com/dsa/problems/binary-tree-coloring-game
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree
---
## 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:**

![](https://assets.glich.co/dsa/binary-tree-coloring-game/image0.png) 

**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**.

# Approaches
## Multiple Traversals (Find then Count)
This approach first locates the node with value `x` and then performs separate traversals to count the nodes in its left and right subtrees. It's a straightforward implementation of the game's logic, breaking the problem down into distinct steps.
**Time:** O(N). Finding node `x` takes O(N). Counting the left and right subtrees can also take up to O(N) each. The total time is O(N) + O(N) + O(N), which simplifies to O(N). However, it traverses parts of the tree multiple times. · **Space:** O(H), where H is the height of the tree. This is for the recursion stack. In the worst case of a skewed tree, H can be N, making the space complexity O(N).
**Pros:** Conceptually simple and easy to understand.; The logic is cleanly separated into finding the node and counting subtrees, making the code easy to follow and debug.
**Cons:** Inefficient due to multiple traversals of the tree or its subtrees.; Nodes in the path to `x` and in its subtrees are visited multiple times across the different function calls, leading to redundant computations.
### Explanation
The core idea is that Player 2 can win if they can secure a region of the tree with more than `n/2` nodes. When Player 1 picks node `x`, the tree is partitioned into three disjoint sets of nodes that Player 2 can choose from: the left subtree of `x`, the right subtree of `x`, and the rest of the tree (connected via `x`'s parent). Player 2's optimal move is to color a node adjacent to `x` (its left child, right child, or parent), as this move effectively claims the entire corresponding region for Player 2. The algorithm implements this logic by first finding node `x`, then counting the sizes of the three potential regions, and finally checking if any region is large enough for a guaranteed win.

```java
class Solution {
    public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
        TreeNode xNode = findNode(root, x);

        int leftCount = countNodes(xNode.left);
        int rightCount = countNodes(xNode.right);
        int parentCount = n - 1 - leftCount - rightCount;

        int half = n / 2;
        return leftCount > half || rightCount > half || parentCount > half;
    }

    private TreeNode findNode(TreeNode node, int val) {
        if (node == null || node.val == val) {
            return node;
        }
        TreeNode leftResult = findNode(node.left, val);
        if (leftResult != null) {
            return leftResult;
        }
        return findNode(node.right, val);
    }

    private int countNodes(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return 1 + countNodes(node.left) + countNodes(node.right);
    }
}
```
### Algorithm
1. **Find Node `x`:** Create a helper function `findNode(node, val)` that performs a standard tree traversal (like DFS) to locate and return the `TreeNode` object with the value `x`. 2. **Count Left Subtree:** Create another helper function `countNodes(node)` that recursively counts the number of nodes in the subtree rooted at `node`. Call this function on `xNode.left` to get `leftCount`. 3. **Count Right Subtree:** Call `countNodes(xNode.right)` to get `rightCount`. 4. **Calculate Parent Region Size:** The number of nodes not in `x`'s own subtree is `parentCount = n - 1 - leftCount - rightCount`. 5. **Check Win Condition:** Player 2 wins if they can secure a region larger than the sum of all other regions. This is true if `leftCount > n / 2`, or `rightCount > n / 2`, or `parentCount > n / 2`. Return `true` if any of these conditions are met, otherwise `false`.

## Optimized Single DFS Traversal
This approach optimizes the process by using a single Depth-First Search (DFS) traversal. It cleverly finds node `x` and counts the sizes of its subtrees simultaneously, avoiding the redundant work of traversing the tree multiple times.
**Time:** O(N). The algorithm traverses the entire tree exactly once. Each node is visited and processed a constant number of times. · **Space:** O(H), where H is the height of the tree, for the recursion stack. In the worst case of a skewed tree, this is O(N).
**Pros:** Highly efficient as it solves the problem in a single pass over the tree.; Optimal time complexity for this problem, as every node must be visited at least once in the worst case.
**Cons:** The logic is more coupled within a single function, which might be marginally harder to read than the multi-traversal approach.; Relies on member variables (or a similar side-effect mechanism) to pass information up from the recursive calls, which can be less clean than a purely functional approach.
### Explanation
This method improves upon the previous one by merging the 'find' and 'count' steps into a single, efficient post-order traversal. We define a recursive helper function that traverses the tree and returns the size of the subtree at the current node. During this traversal, when the function's execution stack returns to the node with value `x`, it has already computed the sizes of its left and right subtrees via the recursive calls. It captures these values and stores them in class-level variables. The main function simply initiates the traversal. After it completes, it uses the stored subtree sizes to calculate the size of the parent region and determine if a winning move exists for Player 2. This avoids re-traversing any part of the tree.

```java
class Solution {
    private int leftCount;
    private int rightCount;
    private int xVal;

    public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
        this.xVal = x;
        // The return value of count is the total number of nodes, which is n.
        // We don't need this value, but the call populates leftCount and rightCount.
        count(root);
        
        int parentCount = n - 1 - leftCount - rightCount;
        
        int half = n / 2;
        return leftCount > half || rightCount > half || parentCount > half;
    }

    private int count(TreeNode node) {
        if (node == null) {
            return 0;
        }
        
        int left = count(node.left);
        int right = count(node.right);
        
        if (node.val == xVal) {
            this.leftCount = left;
            this.rightCount = right;
        }
        
        return 1 + left + right;
    }
}
```
### Algorithm
1. **Use Member Variables:** Define class member variables, `leftCount` and `rightCount`, to store the subtree sizes of node `x` once it's found. 2. **Single Recursive Helper:** Create a single recursive helper function, `count(node)`, that performs a post-order traversal. This function will return the size of the subtree rooted at `node`. 3. **Find and Count:** Inside `count(node)`, after the recursive calls for the left and right children, check if the current `node.val` matches the target value `x`. If it does, update the member variables `this.leftCount` and `this.rightCount` with the sizes returned from the recursive calls on its children. 4. **Return Subtree Size:** The `count(node)` function always returns the total size of the subtree at the current node, which is `1 + leftSize + rightSize`. 5. **Check Win Condition:** The main function initiates the traversal by calling `count(root)`. After the call completes, `leftCount` and `rightCount` will be populated. It then calculates `parentCount` and checks the winning condition `max(leftCount, rightCount, parentCount) > n / 2`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public boolean btreeGameWinningMove ( TreeNode root , int n , int x ) { TreeNode node = dfs ( root , x ); int l = count ( node . left ); int r = count ( node . right ); return Math . max ( Math . max ( l , r ), n - l - r - 1 ) > n / 2 ; } private TreeNode dfs ( TreeNode root , int x ) { if ( root == null || root . val == x ) { return root ; } TreeNode node = dfs ( root . left , x ); return node == null ? dfs ( root . right , x ) : node ; } private int count ( TreeNode root ) { if ( root == null ) { return 0 ; } return 1 + count ( root . left ) + count ( root . right ); } }
```

### JavaScript

```javascript
/** * 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) {
    const dfs = (root) => {
      if (!root || root.val === x) {
        return root;
      }
      return dfs(root.left) || dfs(root.right);
    };
    const count = (root) => {
      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;
  };

```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool btreeGameWinningMove ( TreeNode * root , int n , int x ) { auto node = dfs ( root , x ); int l = count ( node -> left ), r = count ( node -> right ); return max ({ l , r , n - l - r - 1 }) > n / 2 ; } TreeNode * dfs ( TreeNode * root , int x ) { if ( ! root || root -> val == x ) { return root ; } auto node = dfs ( root -> left , x ); return node ? node : dfs ( root -> right , x ); } int count ( TreeNode * root ) { if ( ! root ) { return 0 ; } return 1 + count ( root -> left ) + count ( root -> right ); } };
```

### Python

```python
# 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 : Optional [ TreeNode ], n : int , x : int ) -> bool : def dfs ( root ): if root is None or root . val == x : return root return dfs ( root . left ) or dfs ( root . right ) def count ( root ): if root is None : return 0 return 1 + count ( root . left ) + count ( root . right ) node = dfs ( root ) l , r = count ( node . left ), count ( node . right ) return max ( l , r , n - l - r - 1 ) > n // 2
```