You have n binary tree nodes numbered from 0 to n - 1 where node i has two children leftChild[i] and rightChild[i], return true if and only if all the given nodes form exactly one valid binary tree.
If node i has no left child then leftChild[i] will equal -1, similarly for the right child.
Note that the nodes have no values and that we only use the node numbers in this problem.
Example 1:
Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1] Output: true
Example 2:
Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1] Output: false
Example 3:
Input: n = 2, leftChild = [1,0], rightChild = [-1,-1] Output: false
Constraints:
n == leftChild.length == rightChild.length1 <= n <= 104-1 <= leftChild[i], rightChild[i] <= n - 1In #1361 Validate Binary Tree Nodes, the task is to determine whether the given leftChild and rightChild arrays form exactly one valid binary tree. A valid tree must satisfy three main properties: every node except the root has exactly one parent, there is exactly one root node, and all nodes are connected without forming cycles.
A common strategy is to treat the structure as a directed graph. First, compute the in-degree of each node to ensure no node has more than one parent and to identify the unique root. Then perform a DFS or BFS traversal starting from the root to verify that all nodes are reachable and that no cycles occur.
Another efficient technique uses Union Find to detect cycles and ensure nodes are connected into a single component. Both approaches run in linear time relative to the number of nodes.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DFS / BFS Traversal with In-degree Check | O(n) | O(n) |
| Union Find (Disjoint Set) | O(n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Find the parent of each node.
A valid tree must have nodes with only one parent and exactly one node with no parent.
To solve this problem using the Disjoint Set Union (DSU) approach, we aim to union nodes based on their parent-child relationships. A valid tree should follow these rules:
Time Complexity: O(n), where n is the number of nodes, due to each union and find operation being nearly constant with path compression.
Space Complexity: O(n) for the parent array.
1#include <stdbool.h>
2
3int find(int* parent, int x) {
4 if (parent[x]
The solution creates a parent array to track the roots of each node using the find function with path compression. The unionFind function unites two components. If unionFind finds that two nodes are already connected, it indicates a cycle. The solution verifies each node only has one parent and no cycle exists by unionizing their parent-child relations. Finally, it ensures exactly one node has no parent (root node).
This approach involves calculating the in-degree of each node and checking connectivity via a DFS. The key aspects of a tree like single-root presence and cycle-checking can be managed by:
Time Complexity: O(n), since each node and its immediate edges are evaluated once in each step, including in-drives calculations and DFS.
Space Complexity: O(n) for holding visited tracking and in-degree counts.
void dfs(int node, std::vector<bool>& visited, std::vector<std::vector<int>>& adj) {
if (visited[node]) return;
visited[node] = true;
for (int child : adj[node]) {
dfs(child, visited, adj);
}
}
bool validateBinaryTreeNodes(int n, std::vector<int>& leftChild, std::vector<int>& rightChild) {
std::vector<int> inDegree(n, 0);
std::vector<std::vector<int>> adj(n);
for (int i = 0; i < n; ++i) {
if (leftChild[i] != -1) {
adj[i].push_back(leftChild[i]);
inDegree[leftChild[i]]++;
}
if (rightChild[i] != -1) {
adj[i].push_back(rightChild[i]);
inDegree[rightChild[i]]++;
}
}
int root = -1;
for (int i = 0; i < n; ++i) {
if (inDegree[i] == 0) {
if (root == -1) {
root = i;
} else {
return false;
}
}
}
if (root == -1) return false;
std::vector<bool> visited(n, false);
dfs(root, visited, adj);
for (auto v : visited) {
if (!v) return false;
}
return true;
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems like Validate Binary Tree Nodes are common in technical interviews at companies such as FAANG. They test understanding of trees, graph traversal, cycle detection, and union-find concepts.
An invalid tree occurs if a node has more than one parent, if there are multiple roots or no root, if a cycle exists, or if not all nodes are connected. Any of these conditions breaks the definition of a valid binary tree.
Graph-based data structures work best for this problem. Arrays can track parent counts, while DFS/BFS uses a visited set. Alternatively, the Union Find (Disjoint Set) structure is effective for detecting cycles and verifying connectivity.
A common optimal approach is to compute the in-degree of each node to ensure no node has more than one parent and that exactly one root exists. After identifying the root, perform a DFS or BFS traversal to confirm that all nodes are reachable and no cycles appear.
This solution represents each node and its relationships as directed graph edges, forming an adjacency list adj. It begins by resolving in-degrees to locate the root. The dfs ensures all nodes are explored from the root, confirming all nodes are part of a single, adequately connected component with single ingress from the root.