This question evaluates a candidate's understanding of tree and graph fundamentals, specifically parent-pointer representations, root identification, cycle detection, and connectivity invariants. Commonly asked in the Coding & Algorithms domain to assess reasoning about graph structure and invalid configurations, it requires both conceptual understanding and practical application.
You are given an integer array parent of length n describing a directed parent pointer for each node i (nodes are labeled 0..n-1).
parent[i]
is the parent of node
i
.
parent[root] = -1
.
Determine whether these n nodes form a valid rooted tree.
A valid rooted tree must satisfy all of the following:
i
with
parent[i] = -1
).
parent
: integer array of length
n
where each value is either
-1
or in
[0, n-1]
.
true
if
parent
represents a valid rooted tree; otherwise return
false
.
n
can be 1 (then the only valid tree is
parent[0] = -1
).
parent[i] = i
is invalid.
-1
entries (multiple roots) is invalid.