Practice/Google/Find Root Node in Colored Tree with Pattern Constraints

Find Root Node in Colored Tree with Pattern Constraints

CodingMust

Problem

You are given an undirected connected acyclic graph (a tree) with n nodes labeled from 0 to n-1. Each node is assigned a color represented by a single character. Your task is to find a node that can serve as a valid root such that when the tree is traversed level-by-level starting from that root, all nodes at each depth level match a repeating color pattern.

The pattern is a string that repeats cyclically. For a node at depth d from the root, its color must match pattern[d % len(pattern)]. All nodes at the same depth must satisfy this constraint.

Return the smallest node index that can serve as a valid root. If no such root exists, return -1.

Requirements

1. Build an adjacency list representation of the tree from the given edges
2. For each potential root node, perform a level-order traversal (BFS)
3. At each level during traversal, verify that all nodes match the expected color from the pattern
4. Return the smallest valid root index, or -1 if none exists
5. Each node can have at most 3 connections (degree ≤ 3)

Constraints

• 1 ≤ n ≤ 1000
• edges.length = n - 1 (tree property)
• colors.length = n
• 1 ≤ pattern.length ≤ 10
• Each character in colors and pattern is an uppercase letter (typically 'R', 'B', 'W', etc.)
• The graph is connected and acyclic
• Time complexity: O(n²) is acceptable
• Space complexity: O(n) for the graph representation

Examples

Example 1:

` Input: n = 5, edges = [[0,1],[1,2],[1,3],[3,4]], colors = "RBRRB", pattern = "RB" Output: 0 Explanation: Tree structure: 0(R) | 1(B) /
2(R) 3(R) | 4(B)

From root 0:

• Level 0: [0(R)] → expects R ✓
• Level 1: [1(B)] → expects B ✓
• Level 2: [2(R),3(R)] → expects R ✓
• Level 3: [4(B)] → expects B ✓ Pattern RB repeats: level 0→R, level 1→B, level 2→R, level 3→B `

Example 2:

Input: n = 4, edges = [[0,1],[1,2],[2,3]], colors = "RRRR", pattern = "RB" Output: -1 Explanation: All nodes are Red, but the pattern requires alternating Red and Black colors at different levels. No valid root exists.

Example 3:

` Input: n = 7, edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]], colors = "RBWRBWW", pattern = "RBW" Output: 0 Explanation: From root 0, levels follow pattern RBW cyclically:

• Level 0: [0(R)] → R matches
• Level 1: [1(B),2(W)] → both match their pattern positions
• Level 2: [3(R),4(B),5(W),6(W)] → first three match, but node 6 is W when expecting R%3=0... wait, actually level 2 expects W (position 2 in pattern), so all nodes at level 2 should be W, which fails. This needs node 3,4 to be W. Actually with proper coloring RWWWWWW, root 0 works. `