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.
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.
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.
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.
Community answers
Answer by sourabh.19.cse
public boolean solution(int[] parent) {
int n = parent.length;
if (n == 0) return false;
int root = -1;
int rootCount = 0;
// 1. Find the single root
for (int i = 0; i < n; i++) {
if (parent[i] == -1) {
rootCount++;
root = i;
}
}
if (rootCount != 1) return false;
// 2. Build children lists (parent -> children)
List> children = new ArrayList<>();
for (int i = 0; i < n; i++) children.add(new ArrayList<>());
for (int i = 0; i < n; i++) {
if (i != root) {
// Check for valid parent index
if (parent[i] < 0 || parent[i] >= n) return false;
children.get(parent[i]).add(i);
}
}
// 3. BFS starting from root
Queue queue = new LinkedList<>();
boolean[] visited = new boolean[n];
queue.add(root);
visited[root] = true;
int visitedCount = 0;
while (!queue.isEmpty()) {
int curr = queue.poll();
visitedCount++;
for (int child : children.get(curr)) {
if (visited[child]) return false; // Cycle detected (though impossible with out-degree 1)
visited[child] = true;
queue.add(child);
}
}
// 4. If all nodes were reached, no detached cycles exist
return visitedCount == n;
}
Answer by Josef420
def solution(parent):
roots = []
uncovered_nodes = set()
node_to_children = defaultdict(list)
for node, parent in enumerate(parent):
if parent == -1:
roots.append(node)
uncovered_nodes.add(node)
node_to_children[parent].append(node)
if len(roots) != 1:
return False
visited = set()
que = deque([roots[0]])
while que:
node = que.popleft()
if node in visited:
return False
visited.add(node)
uncovered_nodes.remove(node)
for next_node in node_to_children[node]:
que.append(next_node)
return True if not uncovered_nodes else False