Google New Grad R1: Validate a Tree From Its Parent Array

Role: Software Engineer, New Grad
Result: Passed R1
Report time: February 2026

Coding: validate a parent-array tree

An array specifies the parent of every node. Determine whether the relationships form one valid tree.

The candidate used these conditions:

1. A tree has exactly one root.
2. Every non-root node has one parent, giving n - 1 edges.
3. Every node is reachable from the root.
4. No node is visited twice during traversal, which rules out cycles or multiple paths.

They built an adjacency list, counted roots, and rejected the input when the root count was not one. Otherwise, they traversed from the root with a visited array. A repeated visit made the input invalid; after traversal, any unvisited node also made it invalid.

Practice: Validate a Tree From Its Parent Array

A commenter asked whether “no cycle” meant directed or undirected cycles, but no author clarification was available beyond the parent-array traversal described above.