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:
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 Black or White, find a root such that the graph becomes a binary tree and alternates in color across layers.
Late September, 2024
Intern
In an undirected acyclic graph with a maximum of 3 neighbors per node, find a vertex such that, when suspended from that vertex, the graph becomes a binary tree.
Late September, 2024
Intern
In an undirected acyclic graph with a maximum of 3 neighbors per node, where each node has a value and a specific color, find a vertex such that, when suspended from that vertex, the graph becomes a binary tree satisfying: all adjacent nodes must be of different colors (Red/Black), all nodes at the same level must be of the same color. Return -1 if no such node can be found.
Comments
Hello Interview Premium
Your account is free and you can post anonymously if you choose.