Python - Recursive Solution ✅
The idea is to keep track of the parent nodes of each node first. That will be required when we have to traverse towards the top of a node.\n\nThen, we will che
The idea is to keep track of the parent nodes of each node first. That will be required when we have to traverse towards the top of a node.\n\nThen, we will check how many nodes each subtree has which has root as the node which is the neighbor of the node that "x" selects initially.\n\n\n![image](https://assets.leetcode.com/users/images/74c9e1ff-a80e-4d74-9bb8-14830e773a72_1717564920.3258274.png)\n\n\nFor example, if in the above example, "x" selects the node "3" initially, then "y" has three choices. It can either select node "1" or it can select node "6" or it can select node "7".\n\nThe reason why we want "y" to select neighbors of node "3" is because that will ensure that "y" will get that entire subtree to itself and hence all the nodes. So, if we know the count of nodes in each of these three subtrees rooted at "1", "6" and "7", we can know if "y" has a chance to win or not.\n\nFor example, for the tree with root as "1", the number of nodes are 8 (1,2,4,5,8,9,10,11)\nFor the tree with root as "6", the number of nodes are 1 (6)\nFor the tree with root as "7", the number of nodes are 1 (7)\n\nAnd we see that one subtree has more nodes than other two. It means, if "y" selects the root of this first subtree, then it ensures that "y" will win. Because then, "y" will get all the "8" nodes to itself, whereas "x" will get only 2 more nodes.\n\nAnd that\'s the whole idea.\n\n```\nclass Solution:\n    \n    \n    # To get the data about parent nodes\n    def getParentNodes(self, root, parent, node1, x, parentNodes):\n        \n        # Base Case\n        if not root: return\n        \n        # Update the parent node\n        if parent: parentNodes[root] = parent\n            \n        if root.val == x: node1[0] = root\n            \n        # Traverse left\n        self.getParentNodes(root.left, root, node1, x, parentNodes)\n        \n        # Traverse right\n        self.getParentNodes(root.right, root, node1, x, parentNodes)\n        \n    # Helper function to count nodes in a tree rooted at "root"\n    def count(self, root, node1, parentNodes, visited):\n        \n        # Base Case\n        if not root or root == node1 or root in visited: return 0\n        \n        # Add to the visited set\n        visited.add(root)\n        \n        # Traverse top\n        topCount = 0\n        if root in parentNodes: \n            topCount = self.count(parentNodes[root], node1, parentNodes, visited)\n        \n        # Traverse left\n        leftCount = self.count(root.left, node1, parentNodes, visited)\n        \n        # Traverse right\n        rightCount = self.count(root.right, node1, parentNodes, visited)\n        \n        # Return the total count\n        return topCount + leftCount + 1 + rightCount\n    \n    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n        \n        # To keep track of the parent nodes\n        parentNodes = {}\n        \n        # Also get the node that first player selected\n        node1 = [None]\n        \n        # Traverse the tree and get information about parent nodes\n        self.getParentNodes(root, None, node1, x, parentNodes)\n        \n        # Count of nodes in the subtree with root = parent of node1 (if it is not root itself)\n        countTop = 0\n        if node1[0] in parentNodes: countTop = self.count(parentNodes[node1[0]], node1[0], parentNodes, set())\n        \n        # Count of nodes in the subtree with root = left child of node1 (if it exists)\n        countLeft = self.count(node1[0].left, node1[0], parentNodes, set())\n        \n        # Count of nodes in the subtree with root = right child of node1( (if it exists)\n        countRight = self.count(node1[0].right, node1[0], parentNodes, set())\n        \n        # The second player can only win if among all the three subtrees around the node that "x" has chosen,\n        # One subtree has more nodes than the other two\n        return countTop > countLeft + countRight or countLeft > countTop + countRight or countRight > countTop + countLeft\n```
['Tree', 'Depth-First Search', 'Recursion', 'Binary Tree', 'Python3']