Two players play a turn based game on a binary tree.  We are given the root of this binary tree, and the number of nodes n in the tree.  n is odd, and each node has a distinct value from 1 to n.
Initially, the first player names a value x with 1 <= x <= n, and the second player names a value y with 1 <= y <= n and y != x.  The first player colors the node with value x red, and the second player colors the node with value y blue.
Then, the players take turns starting with the first player.  In each turn, that player chooses a node of their color (red if player 1, blue if player 2) and colors an uncolored neighbor of the chosen node (either the left child, right child, or parent of the chosen node.)
If (and only if) a player cannot choose such a node in this way, they must pass their turn.  If both players pass their turn, the game ends, and the winner is the player that colored more nodes.
You are the second player.  If it is possible to choose such a y to ensure you win the game, return true.  If it is not possible, return false.
 
Example 1:

Input: root = [1,2,3,4,5,6,7,8,9,10,11], n = 11, x = 3
Output: true
Explanation: The second player can choose the node with value 2.

 
Constraints:

root is the root of a binary tree with n nodes and distinct node values from 1 to n.
n is odd.
1 <= x <= n <= 100

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Graph traversal

Starter code: # Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right
class Solution:
    def btreeGameWinningMove(self, root: TreeNode, n: int, x: int) -> bool:
        

Solutions:
class Solution:

	def btreeGameWinningMove(self, root: TreeNode, n: int, x: int) -> bool:

		def count(node):
			if not node:
				return 0
			return 1 + count(node.left) + count(node.right)
		xNode = [0, 0]

		def process(node):
			if node:
				if node.val == x:
					xNode[0] = count(node.left)
					xNode[1] = count(node.right)
				else:
					process(node.left)
					process(node.right)
			return
		process(root)
		player2 = max(xNode[0], xNode[1], n - (xNode[0] + xNode[1] + 1))
		return player2 > n // 2


class Solution:

	def __init__(self):
		(self.lcnt, self.rcnt) = (0, 0)

	def btreeGameWinningMove(self, root: TreeNode, n: int, x: int) -> bool:
		rootCnt = self.dfs(root, x)
		return max([rootCnt - self.lcnt - self.rcnt - 1, self.lcnt, self.rcnt]) > n / 2

	def dfs(self, node: TreeNode, x: int) -> int:
		if not node:
			return 0
		left = self.dfs(node.left, x)
		right = self.dfs(node.right, x)
		if node.val == x:
			self.lcnt = left
			self.rcnt = right
		return 1 + left + right


class Solution:

	def btreeGameWinningMove(self, root: TreeNode, n: int, x: int) -> bool:
		graph = collections.defaultdict(list)
		stack = [root]
		while stack:
			node = stack.pop()
			if node.left:
				graph[node.val].append(node.left.val)
				graph[node.left.val].append(node.val)
				stack.append(node.left)
			if node.right:
				graph[node.val].append(node.right.val)
				graph[node.right.val].append(node.val)
				stack.append(node.right)
		for y in range(1, n + 1):
			if y != x:
				visited = set()
				stack = [x]
				while stack:
					val = stack.pop()
					visited.add(val)
					for nei in graph[val]:
						if nei not in visited and nei != y:
							stack.append(nei)
				if len(visited) <= n // 2:
					return True
		return False


class Solution:

	def btreeGameWinningMove(self, root: TreeNode, n: int, x: int) -> bool:
		c = [0, 0]

		def count(root):
			if not root:
				return 0
			(l, r) = (count(root.left), count(root.right))
			if root.val == x:
				(c[0], c[1]) = (l, r)
			return l + r + 1
		return count(root) / 2 < max(max(c), n - sum(c) - 1)


class Solution:

	def btreeGameWinningMove(self, root: TreeNode, n: int, x: int) -> bool:
		candidates = []

		def dfs(node):
			if not node:
				return 0
			l = dfs(node.left)
			r = dfs(node.right)
			if node.val == x:
				l and candidates.append(l)
				r and candidates.append(r)
			return 1 + l + r
		dfs(root)
		candidates.append(n - (1 + sum(candidates)))
		return any((mine > n - mine for mine in candidates))


class Solution:

	def btreeGameWinningMove(self, root: TreeNode, n: int, x: int) -> bool:

		def countNodes(node):
			left = 0
			if node == None:
				return 0
			if node.left:
				left = countNodes(node.left)
			right = 0
			if node.right:
				right = countNodes(node.right)
			return left + right + 1

		def searchNode(node, x):
			if node.val == x:
				return node
			if node.left:
				tmp = searchNode(node.left, x)
				if tmp:
					return tmp
			if node.right:
				tmp = searchNode(node.right, x)
				if tmp:
					return tmp
			return None
		node = searchNode(root, x)
		left = countNodes(node.left)
		right = countNodes(node.right)
		parent = n - left - right - 1
		if parent > n - parent or left > n - left or right > n - right:
			return True
		return False


class Solution:

	def btreeGameWinningMove(self, root: TreeNode, n: int, x: int) -> bool:
		graph = defaultdict(list)

		def dfs(s):
			if not s:
				return
			for child in [s.left, s.right]:
				if not child:
					continue
				graph[child.val].append(s.val)
				graph[s.val].append(child.val)
				dfs(child)
		dfs(root)
		visited = set()
		visited.add(x)

		def dfs_graph(u):
			res = 1
			visited.add(u)
			for nei in graph[u]:
				if nei not in visited:
					res += dfs_graph(nei)
			return res
		candidates = [dfs_graph(nei) for nei in graph[x]]
		if not candidates:
			return False
		res = max(candidates)
		if res > n - res:
			return True
		else:
			return False


class Solution:

	def btreeGameWinningMove(self, root: TreeNode, n: int, x: int) -> bool:
		if not root:
			return False
		from collections import defaultdict
		graph = defaultdict(list)

		def convert_tree_to_graph(root, parent=None):
			if not root:
				return None
			if parent:
				graph[parent].append(root)
				graph[root].append(parent)
			if root.left:
				convert_tree_to_graph(root.left, root)
			if root.right:
				convert_tree_to_graph(root.right, root)
		convert_tree_to_graph(root)
		node = None
		for (g, v) in list(graph.items()):
			if g.val == x:
				node = g
				break

		def count_nodes_in_subtree(node, visited):
			if node in visited or node.val == x:
				return 0
			visited.add(node)
			count = 0
			for neighbor in graph[node]:
				if neighbor not in visited:
					count += count_nodes_in_subtree(neighbor, visited)
			return count + 1
		subtrees = []
		max_subtree = -1
		for subtree in graph[node]:
			ans = count_nodes_in_subtree(subtree, set())
			subtrees.append(ans)
			max_subtree = max(max_subtree, ans)
		return n - max_subtree < max_subtree
		if not subtrees:
			return False
		if len(subtrees) == 1 and subtrees[0] > 1:
			return True
		return False