class Solution(object):

    left_x = None
    right_x = None
    x = None

    #Time complexity: O(n)
    #Space complexity: O(1)
    def findsubTreeSize(self, root):

        #findsubTreeSize aims to find the total number of nodes of the substree for a given node (containing the node it self)

        if root is None:
            return 0


        left = self.findsubTreeSize(root.left)
        right = self.findsubTreeSize(root.right)

        if root.val == self.x:                
            self.left_x = left
            self.right_x = right


        return left + right + 1

    def btreeGameWinningMove(self, root, n, x):
        """
        :type root: TreeNode
        :type n: int
        :type x: int
        :rtype: bool
        """


        #For the second player, the optimal strategy is to select the node in the neighborhood of the red node 
        #(neighborhood means left child, right child and parent.)
        #The reason is that, by selecting those nodes, it can cut the connection of the red node to the corresponding subtree, so that the red part cannot propagate/diffuse.
        #However, there is no guarantee among the three parts, which part have the most remaining nodes. It needs calculate, which what this algorithm does

        self.x = x   
        self.findsubTreeSize(root)

        return max(n - (self.left_x + self.right_x + 1), max(self.left_x, self.right_x)) > n // 2