Google Software Engineer Intern Interview Experience Valid Tree Problem

Problem statement: Given an array where each element specifies the parent of a node, determine whether the structure forms a valid tree.

Approach: A valid tree must satisfy two conditions: it has exac

Problem statement: Given an array where each element specifies the parent of a node, determine whether the structure forms a valid tree.

Approach: A valid tree must satisfy two conditions: it has exactly n − 1 edges, and there is exactly one simple path from the root to any node. We first build an adjacency list from the input array and count the number of root nodes. If the number of roots is not exactly one, the structure is invalid. Otherwise, we start a DFS from the root. During the traversal, we use a visited array to ensure that each node is visited at most once; if a node is visited more than once, the structure is invalid. After the DFS completes, we check whether there exists any node that was not visited. If all nodes were visited, we return true; otherwise, we return false.