[C++] Simplest - Recursive - 2 solutions.
\n\n\nThis is a game theory question so instead of just making moves, \'blue\' need to  damage \'red\'. \nThe idea is that every node can have at max 3 neighbou
![image](https://assets.leetcode.com/users/images/926fb0de-f0a5-416b-95b5-5b382df1c530_1649934513.5101056.png)\n\n\nThis is a game theory question so instead of just making moves, \'blue\' need to  damage \'red\'. \nThe idea is that every node can have at max 3 neighbour nodes(1> parent, 2> left child, 3> right child), \'red\' node will also have at max 3 neighbours. All these 3 neighbours will further have 3 subtrees, for \'blue\' to win we need to mark one of these neighbours as blue so that one probable path for \'red\' to paint red will be blocked. \n\n1> find red node\n2> count no. of nodes for red node\'s left and right child.\n3> cout no. of nodes to the other side of red node\'s parent node = total no. of nodes(n) - count of nodes in red node\'s left subtree - count of node\'s in red nodes\' right subtree - 1(for red node) \n4> if max of these three count is greater than the sum of other two -> \'blue\' wins.\nHere\'s the simple solution : \n```\nclass Solution {\npublic:\n    int arr[3];\n    bool btreeGameWinningMove(TreeNode* root, int n, int x) {\n        findRedNode(root, x);\n        arr[2] = n - arr[0] - arr[1] - 1;\n        sort(arr, arr+3);\n        \n        if(arr[2] > arr[0] + arr[1]) return true;\n        return false;\n    }\nprivate: \n    void findRedNode(TreeNode* root, int x) {\n        if(root  == NULL) return;\n        \n        if(root -> val == x) {\n            arr[0] = countNodes(root -> left);\n            arr[1] = countNodes(root -> right);\n            return;\n        }\n        \n        findRedNode(root -> left, x);\n        findRedNode(root -> right, x);\n    }\n    \n    int countNodes(TreeNode* node) {\n        if(node == NULL) return 0;\n        return (1+ countNodes(node -> left) + countNodes(node -> right));\n    }\n};\n\n```\n\ntime complexity of this code is just greater than O(n), in order to decrease it we can both find red node plus count nodes to it\'s left and right subtree in one pass as a result time complexity will be under O(n).\n\n\nhere\'s my code: \n```\nclass Solution {\npublic:\n    int arr[3];\n    bool btreeGameWinningMove(TreeNode* root, int n, int x) {\n        findAndCount(root, x);\n        arr[2] = n - arr[0] - arr[1] - 1;\n        sort(arr, arr+3);\n        \n        if(arr[2] > arr[0] + arr[1]) return true;\n        return false;\n    }\nprivate: \n    int findAndCount(TreeNode* root, int x) {\n        if(root == NULL) return 0;\n        int l = findAndCount(root -> left, x);\n        int r = findAndCount(root -> right, x);\n        \n            if(root -> val == x) {\n                arr[0] = l;\n                arr[1] = r;\n            }\n        \n        return l+r+1;\n    }\n    \n};\n\n```
['Backtracking', 'Depth-First Search', 'Recursion', 'Binary Tree']