How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Validate parent array forms a tree | Google Coding Question

Quick Overview

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.

Validate parent array forms a tree

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## 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: 1. **Exactly one root** (exactly one index `i` with `parent[i] = -1`). 2. **No cycles** (following parent pointers from any node must eventually reach the root). 3. **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.

Quick Answer: 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 parent pointer for each node `i` where nodes are labeled `0` to `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 nodes form a valid rooted tree. A valid rooted tree must satisfy all of the following: 1. Exactly one root. 2. No cycles. 3. Every node belongs to the same connected structure and has a path to the root. Return `True` if `parent` represents a valid rooted tree; otherwise return `False`.

Constraints

1 <= n <= 2 * 10^5
Each `parent[i]` is either `-1` or an integer in `[0, n-1]`
`parent[i] = i` is invalid

Examples

Input: [-1, 0, 0, 1, 1]

Expected Output: True

Explanation: Node 0 is the only root. All other nodes are connected under it, and there are no cycles.

Input: [2, -1, 1, 2]

Expected Output: True

Explanation: Node 1 is the root. The paths are 0->2->1, 2->1, and 3->2->1, so every node reaches the same root.

Input: [-1]

Expected Output: True

Explanation: A single node with parent -1 is a valid rooted tree.

Input: []

Expected Output: False

Explanation: An empty array has no root, so it cannot form a valid rooted tree.

Input: [-1, -1, 0]

Expected Output: False

Explanation: There are two roots, so the structure is not a single rooted tree.

Input: [1, 2, 0]

Expected Output: False

Explanation: All nodes form a cycle and there is no root.

Input: [-1, 0, 3, 2]

Expected Output: False

Explanation: Nodes 2 and 3 form a separate cycle, so not all nodes belong to the same rooted structure.

Input: [-1, 0, 5]

Expected Output: False

Explanation: Node 2 points to parent 5, which is outside the valid index range.

Hints

First count how many roots there are. A valid tree must have exactly one `-1` entry.
Build children lists from the parent array, then traverse from the root. If you do not visit every node, the structure is disconnected or contains a cycle away from the root.

Last updated: Apr 23, 2026

Loading coding console...

Quick Overview

Validate parent array forms a tree

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Constraints

1 <= n <= 2 * 10^5
Each `parent[i]` is either `-1` or an integer in `[0, n-1]`
`parent[i] = i` is invalid

Examples

Input: [-1, 0, 0, 1, 1]

Expected Output: True

Explanation: Node 0 is the only root. All other nodes are connected under it, and there are no cycles.

Input: [2, -1, 1, 2]

Expected Output: True

Explanation: Node 1 is the root. The paths are 0->2->1, 2->1, and 3->2->1, so every node reaches the same root.

Input: [-1]

Expected Output: True

Explanation: A single node with parent -1 is a valid rooted tree.

Input: []

Expected Output: False

Explanation: An empty array has no root, so it cannot form a valid rooted tree.

Input: [-1, -1, 0]

Expected Output: False

Explanation: There are two roots, so the structure is not a single rooted tree.

Input: [1, 2, 0]

Expected Output: False

Explanation: All nodes form a cycle and there is no root.

Input: [-1, 0, 3, 2]

Expected Output: False

Explanation: Nodes 2 and 3 form a separate cycle, so not all nodes belong to the same rooted structure.

Input: [-1, 0, 5]

Expected Output: False

Explanation: Node 2 points to parent 5, which is outside the valid index range.

Hints

First count how many roots there are. A valid tree must have exactly one `-1` entry.
Build children lists from the parent array, then traverse from the root. If you do not visit every node, the structure is disconnected or contains a cycle away from the root.

Last updated: Apr 23, 2026

Loading coding console...