0ms | BFS | Diagram | Tree as Graph | Explained
This is a standard simulation problem. You don\'t need to think of all the cases of expansion just deal with the stopping case, i.e. when both red and blue are 
This is a standard simulation problem. You don\'t need to think of all the cases of *expansion* just deal with the **stopping case**, i.e. when both **red** and **blue** are fully expanded leaving no **uncolored** node.\n\n*The key is to imagine this **tree as graph** with parent and childrens as adjacent neighbors *\n\nThe idea is simple we need to pick a **blue** such that **red** can not expand too much : ***count(blue) > count ( red)*** , this is my **winning** condition\n\nYou can observe that if we pick a **blue** immediately next to **red** then *expansion of red is blocked* in that direction so we drastically reduce the number of reds, \n\n# **BUT**\n\n***we have three candidates for blue ( red->left , red->right & red->parent) then which one to pick?***\n\nSolution- Pick a **blue** among these three such that **sum of count** from the rest two nodes +**1** should be still **lesser** than count from the node you\'re painting **blue** \nHere look at this diagram:\n\n![image](https://assets.leetcode.com/users/images/b89d6159-4a6e-4dae-84da-3283fc91c4cc_1665131160.1894546.png)\n\nThis results in **three** cases for winning:\n\n **Case1:** Pick **parent** of x as blue: *Count( left subtree) + Count( right subtree ) + 1(for x) < Count( Parent)*\n \n  **Case2:** Pick **left** of x as blue: *Count( parent subtree) + Count( right subtree ) + 1< Count( Left)*\n  \n   **Case3:** Pick **right** of x as blue: *Count( left subtree) + Count( parent subtree ) + 1< Count( Right)*\n \n\nIf any of case becomes **true** we can return **true **\n\nelse  return **false** \n\n# Code:\n\n```\nclass Solution {\npublic:\n    TreeNode* rootx;\n    unordered_map<int, TreeNode*> mp;\n    \n    \n    int bfs(TreeNode* root){\n        \n        queue<TreeNode*> q; q.push(root);\n        int count=0;\n        if(!root) return 0;\n        \n        while(!q.empty()){\n            auto curr=q.front();q.pop();\n            int t=curr->val;\n            curr->val=0;\n            count++;\n            \n            if(curr->left && curr->left->val!=0 ) q.push(curr->left);\n            if(curr->right && curr->right->val!=0  ) q.push(curr->right);\n            if(mp[t] && mp[t]->val!=0  ) q.push(mp[t]);\n        }\n        \n        return count;\n    }\n    \n    void preorder(TreeNode* root,int x){\n        \n        if(!root) return;\n        \n        if(root->val==x) rootx=root;\n        if(root->left) mp[root->left->val]=root;\n        if(root->right) mp[root->right->val]=root;\n        preorder(root->left,x);\n        preorder(root->right,x);\n    }\n    \n    bool btreeGameWinningMove(TreeNode* root, int n, int x) {\n        \n        preorder(root,x);\n        mp[root->val]=NULL;\n        \n        rootx->val=0;\n        int a=bfs(mp[x]);\n        int b=bfs(rootx->left);\n        int c=bfs(rootx->right);\n        \n        if(a+b+1<c) return true;\n        \n        if(b+c+1<a) return true;\n        \n        if(c+a+1<b) return true;\n        \n        return false;\n    }\n};\n\n\n```\n\n**If you like the explanation then feel free to upvote. Cheers!!**
['Tree', 'Breadth-First Search', 'Graph']