C++ beat 100%, explained
The trick here is in order to optimally choose y, there are only 3 options\n1) parent node of x\n2) left child of x\n3) right child of x\n\nNote that once we ch
The trick here is in order to optimally choose y, there are only 3 options\n1) parent node of x\n2) left child of x\n3) right child of x\n\nNote that once we choose y, the tree is "split" into 2 subtrees (you can think of cutting the edge connecting x and y).\nthe following actions of 2 players are constrained within their correspoding subtree. Therefore, the comparing the sizes of subtrees determines whether the second player can win.\n\n```\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n * };\n */\nclass Solution {\npublic:\n    int count(TreeNode* root) {\n        if(!root) return 0;\n        return 1 + count(root->left) + count(root->right);\n    } \n    \n    TreeNode* find(TreeNode* root, int x) {\n        if(!root) return nullptr;\n        if(root->val == x) return root;\n        \n        auto n = find(root->left, x);\n        if(n) return n;\n        n = find(root->right, x);\n        return n;\n    }\n    \n    bool btreeGameWinningMove(TreeNode* root, int n, int x) {\n        TreeNode* node = find(root, x);\n        \n        int left = count(node->left);\n        int right = count(node->right);\n        int threshold = n / 2;\n        \n        if(left > threshold || right > threshold || (n - 1 - left - right) > threshold) {\n            return true;\n        }\n        return false;\n    }\n};\n```
[]