Practice/Google/Convert Graph to Binary Tree with Alternating Colors

Convert Graph to Binary Tree with Alternating Colors

CodingMust

Problem

You are given an undirected connected acyclic graph (a tree structure) where each node can have at most three connections. Each node is assigned a color represented by an integer (typically 0 or 1, representing two distinct colors).

Your task is to determine if there exists a root node such that when you treat the graph as a rooted tree starting from that node, the following properties hold:

1. All nodes at the same depth level have identical colors
2. Nodes at adjacent depth levels have different colors
3. Each non-leaf node has at most two children (forming a binary tree structure)

If such a root exists, return the smallest valid root node index. If no valid root exists, return -1.

Requirements

1. Process an undirected graph with n nodes (indexed from 0 to n-1)
2. Each node has a color value (0 or 1)
3. Check each potential root to see if it satisfies the level-coloring property
4. Return the smallest valid root index, or -1 if none exists
5. The resulting tree must be binary (each node has at most 2 children)

Constraints

• 1 ≤ n ≤ 1000
• edges.length = n - 1 (the graph is a tree)
• Each node has at most 3 edges
• colors[i] is either 0 or 1
• The graph is connected and acyclic
• Time complexity should be O(n²) or better
• Space complexity should be O(n)

Examples

Example 1:

Input: n = 4, edges = [[0, 1], [1, 2], [1, 3]], colors = [0, 1, 0, 0] Output: 0 Explanation: When rooted at node 0: Level 0: node 0 (color 0) Level 1: node 1 (color 1) Level 2: nodes 2, 3 (both color 0) All nodes at each level have the same color, and adjacent levels differ.

Example 2:

Input: n = 5, edges = [[0, 1], [1, 2], [2, 3], [3, 4]], colors = [0, 1, 0, 1, 1] Output: -1 Explanation: This is a chain of nodes. No matter which node is selected as root, the constraints cannot be satisfied.

Example 3:

Input: n = 1, edges = [], colors = [0] Output: 0 Explanation: A single node trivially satisfies all requirements.