Google·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Google SWE interview with a graph/tree problem that had a color-uniformity twist. The structural part was familiar enough but the follow-up added a layer I hadn't really prepped for.

Questions Asked (1)

Given an undirected graph where each node has a color (black or white), determine whether the graph can be interpreted as a valid binary tree rooted at some node such that every level of the tree contains only nodes of the same color.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The base problem (is this undirected graph a valid binary tree) I'd seen before, so I got through the structural check okay.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as checking whether the graph can be partitioned into color-consistent levels via BFS from a candidate root, ensuring each level is monochromatic and edges only connect adjacent levels. Use the fact that in a valid tree, the root must be the unique node at distance 0, and all nodes at the same distance must share the same color. Validate by checking that the graph is connected, acyclic, and that BFS layers alternate colors consistently.

Pro tip: Clarify that the graph must be a tree (connected and acyclic) and that the root's color determines the color of all nodes at even distances, while the opposite color appears at odd distances. This reduces the problem to checking bipartiteness with respect to the root's color.

1. Understand the problem and constraints

Restate the problem: given an undirected graph with colored nodes, determine if there exists a root such that the graph is a tree and each level (by distance from root) is monochromatic. Note that the graph must be connected and acyclic.

2. Identify necessary conditions

For a valid tree, the graph must be connected and have exactly n-1 edges. Also, the colors must alternate by level: all nodes at even distance from root have one color, and all at odd distance have the other. Thus, the graph must be bipartite with respect to the root's color.

3. Design an algorithm

Try each node as a potential root. For each root, perform BFS to assign levels and check that all nodes at the same level have the same color, and that no edges connect nodes at the same level or skip levels. Alternatively, use the fact that the root's color determines the color of all nodes at even/odd distances, and check if the graph is bipartite with that coloring.

4. Optimize and analyze complexity

Naively trying all roots takes O(n*(n+m)). Optimize by observing that the root must be a node whose color matches the majority color at even distances. Use BFS from any node to determine the two possible colorings, then check if either matches the given colors. This reduces to O(n+m).

5. Handle edge cases and validate

Consider edge cases: single node (always valid), disconnected graph (invalid), cycles (invalid), and graphs where multiple roots could work. Validate the solution with examples and discuss trade-offs between different approaches.

Key Points to Mention

The graph must be a tree: connected and acyclic (exactly n-1 edges).
Levels correspond to BFS layers from the root; all nodes at the same distance must have the same color.
The root's color determines the color of all nodes at even distances; the opposite color appears at odd distances.
The problem reduces to checking if the graph is bipartite with a coloring that matches the given node colors, possibly after swapping colors.
Time complexity: O(n+m) if optimized, O(n*(n+m)) if trying all roots naively.
Edge cases: single node, disconnected graph, cycles, and multiple valid roots.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.