Simple recursive solution in C++ with explanation [0ms]
Because the game is played on a tree there are no cycles in the graph, and marking a node divides-off a part of the graph, making it forever inaccessible to the
Because the game is played on a tree there are no cycles in the graph, and marking a node divides-off a part of the graph, making it forever inaccessible to the other player. Therefore, a first move which cuts off more of the tree than remains accessible to the other player is an automatic winning one. The best such move must be adjacent to the selection of the first player because any other move will always increase the number of nodes it cuts off if it is adjusted towards the node chosen by player one by one edge in the graph.\n\nOur choice is therefore between the zero to three neighbouring nodes of the node chosen by player 1. We can evaluate which of these is best by counting the nodes connected through them. The left and right subtrees can be counted by a simple recursive depth first search. The part of the tree connected through the parent of this node can be counted implcitly since we were given the total node count in parameter _n_.  We simply subtract the left and right subtree counts from _n_ and one more for the node chosen by player 1 to give the number of nodes reachable through the parent. \n\n### Algorithm \n\n*   Search the tree for the node of the player\'s first move.\n*   Walk the tree down the the left and right branches from that, counting nodes in each.\n*   There will be up to 3 groups of nodes:\n    *   left:   counted\n\t*   right:  counted:\n\t*   parent: n - (left + right + 1);\n\nIf one of these counts is larger than the other two combined,  there exists a move separating that subtree from player 1 which means player one can never win no matter what other moves follow.\n\n### C++ Code\n\n```c++\n    constexpr const TreeNode* find(const TreeNode* node, const int val){\n        if(node->val == val) return node;\n\t\t\n        const TreeNode* found = nullptr; \n        if(node->left) found = find(node->left, val);\n        if(!found && node->right) found = find(node->right, val);\n        return found;\n    }\n    \n    constexpr const unsigned count(const TreeNode* node){\n        unsigned counter = 1;\n        if(node->left) counter += count(node->left);\n        if(node->right) counter += count(node->right);\n        return counter;\n    }\n    \n    class Solution {\n    public:\n        constexpr\n        bool btreeGameWinningMove(TreeNode* root, int n, int x) const\n        {\n            const TreeNode*const p1_move = find(root, x);\n            const unsigned left_count  = p1_move->left  != nullptr ? count(p1_move->left)  : 0;\n            const unsigned right_count = p1_move->right != nullptr ? count(p1_move->right) : 0;\n            const unsigned parent_count = n - (left_count + right_count + 1);\n            if(left_count   > 1 + parent_count + right_count ||\n               right_count  > 1 + parent_count + left_count  ||\n               parent_count > 1 + left_count + right_count)\n            {\n                return true;\n            }\n            return false;\n        }\n    };\n```
['Depth-First Search', 'Recursion', 'C', 'Binary Tree']