Can you beat this game? Google Interview Question: Binary Tree Coloring Game

Here’s a question that Google asked in its interview process. I’ve pasted the problem statement below.

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.

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.

Clarifying the Question

Let’s be explicit about what the question is asking for:

• The first player selects which node to color red, which is their color.
• We (blue) always make the second move and select which node to color blue, which is our color.
• Is there a move to guarantee that we (blue) win?

Note that a player can only color an uncolored node that’s a neighbor of the chosen node. So in the picture above, on the next turn, the red player can only select 1, 6, or 7. As the blue player, I can’t select any of those nodes.

Intuition

It’s not immediately obvious to me what the best way to play the game is. Let’s study the example given:

• The first move is to color node 3 red.
• If I pick node 6 or 7, I’m stuck, because I can’t color any other nodes in this game after this move.
• Node 1 looks like a good move though. I’m forcing the red player to only pick nodes 6 or 7 after.

Aha! So maybe it is pretty straightforward — I’ll want to always pick an adjacent node to the first red node, to “block” them off from picking any other nodes that are connected to my selected node.

What are my options for the second move? I could select the left child, right child, or parent of the first selected red node for my second move. And, that’s really the only decision I’m making in this game; I can’t “cross” over to any of the red node’s territory.

So I want to select the node out of [left child, right child, parent] that has the most nodes in its “subtree.”

But how do I know it’s a winning move?

This takes some thought. Let’s play with a simpler example:

What are some possible first moves? The first player can color the following nodes red:

• Node 4: Then we can color node 2 blue, and red can only capture 1 node.
• Node 5: Same reasoning as node 4 above.
• Node 2: We can color node 1 blue, and red will only have 3 nodes.
• Node 1: We can color node 2 or 3 blue, and red will win with 4 nodes captured compared to 3 blue nodes.
• Nodes 3, 6, and 7 are symmetrical to nodes 2, 4, and 5 (respectively), so the same logic holds.

So the best that red can do is take n/2 + 1 nodes (our problem statement says there is an odd number of nodes). So we can check that the number of nodes that are part of the subtree that we (blue) select is greater than n/2.

How do we implement the logic for the parent though? Well, if n is the total number of nodes, then n - 1 - count_left - count_right is the number of nodes in the parent subtree. Stare at that expression for a bit— does it make sense?

• We subtract 1 for the selected red node.
• count_left is the number nodes in the left subtree of the red node.
• count_right is the number of nodes in the right subtree of the right node.

Our psuedocode might look like:

n = number of nodes (this is given to us)
if (count of nodes in left subtree) > n/2 or 
  (count of nodes in right subtree) > n/2 or 
  n - 1 - count_left - count_right > n/2:
  return True

The code

class Solution(object):
    def btreeGameWinningMove(self, root, n, x):
        """
        :type root: TreeNode
        :type n: int
        :type x: int
        :rtype: bool
        """
        def get_count_nodes_in_subtree(node):
            if not node:
                return 0
            return 1 + get_count_nodes_in_subtree(node.left) + get_count_nodes_in_subtree(node.right)
    
        # find the number of nodes in each subtree of the first selected node's neighbors.
        self.l, self.r = 0,0
        def traverse(node):
            if not node:
                return 0
            if node.val != x: # we haven't found the target node, so check left and right
                traverse(node.left)
                traverse(node.right)
            else: # we found our target node, so do the counting
                self.l = get_count_nodes_in_subtree(node.left)
                self.r = get_count_nodes_in_subtree(node.right)

        traverse(root)
        if self.l > n/2 or self.r > n/2: # we could select the left or right node
            return True
        if n - 1 - self.l - self.r > n/2: # we select the parent node
            return True
        return False

Time and space complexity

Time complexity: O(N), since we traverse the tree once.

Space complexity: O(N), for the recursive call stack.