Validate parent array forms a tree

Q: Validate parent array forms a tree

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Problem

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 .
Exactly one node should be the root, indicated by parent[root] = -1 .

Determine whether these n nodes form a valid rooted tree.

A valid rooted tree must satisfy all of the following:

Exactly one root (exactly one index i with parent[i] = -1 ).
No cycles (following parent pointers from any node must eventually reach the root).
Connectivity (every node is reachable from the root; equivalently, every node has exactly one simple path to the root).

Input

parent : integer array of length n where each value is either -1 or in [0, n-1] .

Output

Return true if parent represents a valid rooted tree; otherwise return false .

Notes / Edge Cases

n can be 1 (then the only valid tree is parent[0] = -1 ).
Self-parenting like parent[i] = i is invalid.
Multiple -1 entries (multiple roots) is invalid.
A cycle among non-root nodes is invalid.
A disconnected component (some nodes not reachable from the root) is invalid.

Validate parent array forms a tree

Quick Overview

Problem

Input

Output

Notes / Edge Cases

Comments (0)