Google·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Apr 2026

Summary

Google SWE interview with a tree validation problem. Pretty standard algorithmic round but the edge cases kept me second-guessing myself the whole time.

Questions Asked (1)

You're given an array where each index represents a node and the value at that index is its parent (with -1 or similar sentinel marking the root). Determine if this structure forms a valid tree.

Algorithms & Data Structures

Author's notes

The core conditions aren't hard to list out: exactly one root, n-1 edges, no cycles, fully connected.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the parent array as a directed graph and verify it satisfies the necessary and sufficient conditions for a tree: exactly one root, no cycles, and all nodes connected. Use a union-find or DFS approach to detect cycles and count components, ensuring the edge count is exactly n-1.

Pro tip: Clarify edge cases upfront—empty array, multiple roots, self-loops, and disconnected components—and mention that a valid tree must have exactly n-1 edges and no cycles. This shows you think about correctness and boundary conditions before coding.

1. Clarify assumptions and edge cases

Confirm the sentinel value for root (e.g., -1), whether the array can be empty, and if multiple roots are allowed. Discuss edge cases like self-loops and disconnected nodes.

2. Check basic invariants

Verify there is exactly one root (one node with sentinel parent) and that every non-root parent index is within bounds. Also, ensure no node is its own parent.

3. Detect cycles and connectivity

Use union-find or DFS to detect cycles and count connected components. A valid tree must have exactly one component and no cycles.

4. Validate edge count

Confirm that the number of edges (n-1) matches the number of nodes minus one, which is a necessary condition for a tree.

5. Combine checks and return result

If all conditions hold (one root, no cycles, one component, n-1 edges), return true; otherwise, false. Explain time and space complexity.

Key Points to Mention

A valid tree must have exactly one root (one node with parent -1).
No cycles are allowed; use union-find or DFS to detect cycles.
All nodes must be connected (exactly one connected component).
The number of edges must be exactly n-1 (where n is the number of nodes).
Handle edge cases: empty array, multiple roots, self-loops, and out-of-bounds parent indices.
Time complexity: O(n) with union-find or DFS; space complexity: O(n).

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