Tap here to switch tabs
Problem
Submissions

Problem: Binary Tree Coloring Game

Try to solve the Binary Tree Coloring Game problem.

Statement

Two players play a turn based game on a binary tree with n nodes, where each node has a unique value from 11 to n. The total number of nodes n is odd.

Initially, the first player chooses a node with value x and colors it red. The second player then chooses any other node with value y where y \neq x and colors it blue.

On each subsequent turn, a player may select an uncolored node that is directly adjacent (a parent, left child, or right child) to any node they have already colored, and color it with their respective color. A player must pass their turn if no such adjacent uncolored node exists. The game concludes when neither player can make any more moves.

The winner is the player who has colored more nodes.

Given the root of the binary tree, the number of nodes n, and the first player’s chosen value x, return true if the second player can choose a node y that guarantees their victory, or false otherwise.

Constraints:

  • The number of nodes in the tree is n.

  • 1≤1 \leq x ≤\leq n ≤100\leq 100

  • n is odd.

  • 1≤1 \leq Node.val ≤\leq n

  • All the values of the tree are unique.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Binary Tree Coloring Game

Try to solve the Binary Tree Coloring Game problem.

Statement

Two players play a turn based game on a binary tree with n nodes, where each node has a unique value from 11 to n. The total number of nodes n is odd.

Initially, the first player chooses a node with value x and colors it red. The second player then chooses any other node with value y where y \neq x and colors it blue.

On each subsequent turn, a player may select an uncolored node that is directly adjacent (a parent, left child, or right child) to any node they have already colored, and color it with their respective color. A player must pass their turn if no such adjacent uncolored node exists. The game concludes when neither player can make any more moves.

The winner is the player who has colored more nodes.

Given the root of the binary tree, the number of nodes n, and the first player’s chosen value x, return true if the second player can choose a node y that guarantees their victory, or false otherwise.

Constraints:

  • The number of nodes in the tree is n.

  • 1≤1 \leq x ≤\leq n ≤100\leq 100

  • n is odd.

  • 1≤1 \leq Node.val ≤\leq n

  • All the values of the tree are unique.