Convert Graph to Binary Tree with Alternating Colors
Given an undirected connected acyclic graph where each node has at most 3 edges, and nodes are colored (either Black/White or Red/Black), find a root vertex such that when the graph is suspended from that vertex, it becomes a binary tree where all nodes at the same level have the same color, and adjacent levels have different colors. Return -1 if no such vertex exists.
Asked at:
Google
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
0
Early January, 2025
Mid-level
Given an undirected connected acyclic graph where each node has at most 3 edges, and nodes are colored Black or White, find a root such that the graph becomes a binary tree and alternates in color across layers.
Hello Interview Premium
Your account is free and you can post anonymously if you choose.