Binary Tree Coloring Game

Medium
1941.

Binary Tree Coloring Game

Binary Tree Coloring Game is a medium coding problem on depth-first search and trees, asked in Amazon and Google interviews.

Two players play a turn-based game on a binary tree. You are given its root and the number of nodes n, which is odd; the nodes hold the distinct values 1 to n.

The first player picks a value x and colors that node red. The second player then picks a different value y and colors that node blue. After that the players alternate, starting with the first: on a turn a player picks a node of their own color and colors one of its uncolored neighbours (its left child, right child or parent). A player who cannot move passes. When both players must pass the game ends, and whoever colored more nodes wins.

You are the second player and x has been chosen. Return true if you can choose y so that you are guaranteed to win, and false otherwise.

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 colors 2. Node 3 then cuts the red side off from 1, 2 and 2's whole subtree — 6 of the 11 nodes go blue.

Example 2

Input
root = [1,2,3], n = 3, x = 1
Output
false
Explanation
Red holds the root; blue can take only one of the two leaves, 1 node against red's 2.

Example 3

Input
root = [1,2,3], n = 3, x = 2
Output
true
Explanation
Blue colors 1 and then reaches 3 as well: 2 nodes against red's 1.

Constraints

  • 1 <= n <= 100
  • n is odd
  • the tree has n nodes with the distinct values 1 to n
  • 1 <= x <= n
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} n
 * @param {number} x
 * @return {boolean}
 */
var btreeGameWinningMove = function(root, n, x) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Binary Tree Coloring Game — Solution in Python, Java & C++

Binary Tree Coloring Game solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Binary Tree Coloring Game is a medium coding problem on depth-first search and trees, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Depth-First Search, Trees
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Two players play a turn-based game on a binary tree. You are given its root and the number of nodes n, which is odd; the nodes hold the distinct values 1 to n.

The first player picks a value x and colors that node red. The second player then picks a different value y and colors that node blue. After that the players alternate, starting with the first: on a turn a player picks a node of their own color and colors one of its uncolored neighbours (its left child, right child or parent). A player who cannot move passes. When both players must pass the game ends, and whoever colored more nodes wins.

You are the second player and x has been chosen. Return true if you can choose y so that you are guaranteed to win, and false otherwise.

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 colors 2. Node 3 then cuts the red side off from 1, 2 and 2's whole subtree — 6 of the 11 nodes go blue.

Example 2

Input: root = [1,2,3], n = 3, x = 1
Output: false
Explanation: Red holds the root; blue can take only one of the two leaves, 1 node against red's 2.

Example 3

Input: root = [1,2,3], n = 3, x = 2
Output: true
Explanation: Blue colors 1 and then reaches 3 as well: 2 nodes against red's 1.

Constraints

  • 1 <= n <= 100
  • n is odd
  • the tree has n nodes with the distinct values 1 to n
  • 1 <= x <= n

Hints for Binary Tree Coloring Game

  1. Hint 1

    Removing the red node splits the tree into at most three regions: its left subtree, its right subtree, and everything above it.

  2. Hint 2

    If blue starts next to red in one of those regions, red can never enter that region — the only way in is through red's own node, which blue has blocked.

  3. Hint 3

    So blue wins exactly when one of the three regions holds more than half of the n nodes. Count the two subtree sizes of x; the third region is what is left.

How to solve Binary Tree Coloring Game

Blue's best move is to stand on one of red's neighbours, sealing off that neighbour's whole region. The three regions around x have sizes left, right and n - 1 - left - right, and blue wins iff the largest is more than n / 2.

Approach

  1. Walk the tree computing every subtree's size.
  2. At the node whose value is x, record the sizes of its left and right subtrees.
  3. The region above x has n - 1 - left - right nodes.
  4. Return whether the largest of the three regions times 2 exceeds n.

Why it works

The regions around x touch each other only through x, which red owns. Blue choosing the neighbour of x in a region claims that entire region: red cannot get into it, and blue can spread through it one node per turn. Red can at best claim everything else. Choosing a node farther from x only gives red a chance to take more, so the neighbour of the largest region is optimal, and blue wins iff that region alone is a majority (n is odd, so there are no ties).

Complexity

  • Time — O(n)
  • Space — O(h) for the recursion

Pitfalls

  • Do not forget the parent region — when x is deep, the part above it is often the largest.
  • Strictly more than half: compare 2 · size > n.

Reference solution

Python

from typing import Optional

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

    def count(node):
        if node is None:
            return 0
        a = count(node.left)
        b = count(node.right)
        if node.val == x:
            sides[0] = a
            sides[1] = b
        return a + b + 1

    count(root)
    above = n - 1 - sides[0] - sides[1]
    return 2 * max(above, sides[0], sides[1]) > n

Java

public static boolean btreeGameWinningMove(TreeNode root, int n, int x) {
    int[] sides = new int[2];
    countSides(root, x, sides);
    int above = n - 1 - sides[0] - sides[1];
    return 2 * Math.max(above, Math.max(sides[0], sides[1])) > n;
}

static int countSides(TreeNode node, int x, int[] sides) {
    if (node == null) return 0;
    int a = countSides(node.left, x, sides);
    int b = countSides(node.right, x, sides);
    if (node.val == x) { sides[0] = a; sides[1] = b; }
    return a + b + 1;
}

C++

int countSides(TreeNode* node, int x, int& left, int& right);

bool btreeGameWinningMove(TreeNode* root, int n, int x) {
    int left = 0, right = 0;
    countSides(root, x, left, right);
    int above = n - 1 - left - right;
    return 2 * max(above, max(left, right)) > n;
}

int countSides(TreeNode* node, int x, int& left, int& right) {
    if (!node) return 0;
    int a = countSides(node->left, x, left, right);
    int b = countSides(node->right, x, left, right);
    if (node->val == x) { left = a; right = b; }
    return a + b + 1;
}

JavaScript

var btreeGameWinningMove = function(root, n, x) {
    var sides = [0, 0];
    countSides(root, x, sides);
    var above = n - 1 - sides[0] - sides[1];
    return 2 * Math.max(above, sides[0], sides[1]) > n;
};

var countSides = function(node, x, sides) {
    if (node === null) return 0;
    var a = countSides(node.left, x, sides);
    var b = countSides(node.right, x, sides);
    if (node.val === x) { sides[0] = a; sides[1] = b; }
    return a + b + 1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals