Your Dashboard
Interview Coaching
Learn
System Design
ML System Design
Code
Behavioral
Salary Negotiation
Interview Guides
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.