Find Root Node in Colored Tree with Pattern Constraints
Given an undirected connected acyclic graph where each node has at most 3 edges and nodes are colored (Red/Black/White or similar color patterns), find a root node such that when the graph is viewed as a binary tree from that root, it satisfies specific color pattern constraints across levels (e.g., RBWRBW repeating pattern or alternating colors). Return -1 if no valid root exists.
Asked at:
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Early January, 2025
Mid-level
Given an undirected connected acyclic graph where each node has at most 3 edges, and nodes are colored Red (R), Blue (B), or White (W), find a root such that the graph becomes a binary tree and the layers follow a fixed color sequence (e.g., RBWRBW).
Late September, 2024
Mid-level
Find a root vertex in an undirected acyclic graph with specific color constraints: Vertices have at most 3 neighbors, are colored red/black/white, same depth vertices have same color, colors change in R->W->B->R->W->B order as depth increases, and the resulting structure forms a valid binary tree. Return -1 if no such vertex exists.
Early August, 2024
Mid-level
Find a valid root node in a colored tree. Given a tree with n nodes, each colored 'R', 'A', or 'W', determine if there exists a node that can serve as the root of a binary tree such that the colors follow one of six possible repeating 3-color patterns level by level. Return the index of a valid root node if it exists, or -1 if no solution exists. The tree has at most 3 neighbors per node, and the time complexity should be O(V).
Comments
Hello Interview Premium
Your account is free and you can post anonymously if you choose.