Binary Tree Coloring Game

MediumTreesdfs

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

A binary tree has n nodes (with n odd) whose values are exactly 1 through n. Two players play a game on it. The first player picks the node with value x and colors it red. The second player then picks a different node y and colors it blue. Players alternate turns, starting with the first player. On a turn, a player picks one of their own colored nodes and colors an uncolored neighbor (its parent, left child or right child) in their color. A player with no legal move passes. The game ends when both players pass, and whoever colored more nodes wins. You are the second player. Given root, n and x, return true if there is a choice of y that guarantees you win no matter how the first player plays, and false otherwise.

Examples

Input: root = [1,2,3,4,5], n = 5, x = 1
Output: true
Pick y = 2. Red cannot get past blue into {2, 4, 5}, so blue ends with 3 nodes and red with 2.
Input: root = [1,2,3,4,5], n = 5, x = 2
Output: false
Removing node 2 leaves pieces of sizes 1, 1 and 2. Blue can claim at most one piece, never more than 2 of 5 nodes.
Input: root = [1,2,3], n = 3, x = 1
Output: false
Whichever child blue takes, blue gets 1 node and red gets 2.

Constraints

  • 1 <= n <= 100
  • `n` is odd
  • The tree has exactly `n` nodes with values `1` through `n`, each used once
  • 1 <= x <= n

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More dfs problems