<p>Two players play a turn based game on a binary tree. We are given the <code>root</code> of this binary tree, and the number of nodes <code>n</code> in the tree. <code>n</code> is odd, and each node has a distinct value from <code>1</code> to <code>n</code>.</p>

<p>Initially, the first player names a value <code>x</code> with <code>1 &lt;= x &lt;= n</code>, and the second player names a value <code>y</code> with <code>1 &lt;= y &lt;= n</code> and <code>y != x</code>. The first player colors the node with value <code>x</code> red, and the second player colors the node with value <code>y</code> blue.</p>

<p>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 <strong>uncolored</strong> neighbor of the chosen node (either the left child, right child, or parent of the chosen node.)</p>

<p>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.</p>

<p>You are the second player. If it is possible to choose such a <code>y</code> to ensure you win the game, return <code>true</code>. If it is not possible, return <code>false</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2019/08/01/1480-binary-tree-coloring-game.png" style="width: 500px; height: 310px;" />
<pre>
<strong>Input:</strong> root = [1,2,3,4,5,6,7,8,9,10,11], n = 11, x = 3
<strong>Output:</strong> true
<strong>Explanation: </strong>The second player can choose the node with value 2.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> root = [1,2,3], n = 3, x = 1
<strong>Output:</strong> false
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li>The number of nodes in the tree is <code>n</code>.</li>
	<li><code>1 &lt;= x &lt;= n &lt;= 100</code></li>
	<li><code>n</code> is odd.</li>
	<li>1 &lt;= Node.val &lt;= n</li>
	<li>All the values of the tree are <strong>unique</strong>.</li>
</ul>

class Solution {
public:
    TreeNode* findX(TreeNode* curr, int x) {

        if (!curr || curr->val == x) {
            return curr;
        }

        TreeNode* serachLeft = findX(curr->left, x);

        return serachLeft ? serachLeft : findX(curr->right, x);
    }

    int countNodes(TreeNode* curr) {

        if (!curr) {
            return 0;
        }
        return 1 + countNodes(curr->left) + countNodes(curr->right);
    }

    bool btreeGameWinningMove(TreeNode* root, int n, int x) {
        
        // Find x (target) in the tree
        TreeNode* target = findX(root, x);

        // Count the nodes in the left and right subtrees of the target node
        int countLeft = countNodes(target->left);
        int countRight = countNodes(target->right);

        // The parent partition's node count (UPPER) (n-left-right-1), -1 for current node
        int countUpper = n - countLeft - countRight - 1;

        // A winning move is possible if any partition
        //  has more than half of the total nodes
        return max({countLeft, countRight, countUpper}) > n / 2;
    }
};
13000