Validate Binary Tree Nodes — Solution in Python, Java & C++
Validate Binary Tree Nodes solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Validate Binary Tree Nodes is a medium coding problem on depth-first search, breadth-first search and trees, asked in Amazon and Meta interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Breadth-First Search, Trees, Graph, Union Find
- Asked at: Amazon, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You have n binary tree nodes numbered 0 to n - 1. Node i has left child leftChild[i] and right child rightChild[i], where -1 means the child is missing.
Return true if all the given nodes form exactly one valid binary tree, and false otherwise.
The nodes carry no values — only the links matter.
Example 1
Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
Output: true
Explanation: 0 is the root with children 1 and 2; node 3 hangs under 2.
Example 2
Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1]
Output: false
Explanation: Node 3 has two parents, 1 and 2.
Example 3
Input: n = 2, leftChild = [1,0], rightChild = [-1,-1]
Output: false
Explanation: 0 and 1 point at each other: a cycle with no root.
Constraints
n == leftChild.length == rightChild.length1 <= n <= 10^4-1 <= leftChild[i], rightChild[i] <= n - 1
Hints for Validate Binary Tree Nodes
Hint 1
In a valid tree exactly one node — the root — has no parent, and every other node has exactly one.
Hint 2
Count each node's parents. Any node with two parents fails immediately; zero or several parentless nodes fail too.
Hint 3
Parent counts alone miss a separate cycle (e.g.
1 → 2 → 1beside a valid tree). From the unique root, traverse the children and check that allnnodes are reached.
How to solve Validate Binary Tree Nodes
A valid binary tree is a rooted tree: one node with in-degree 0, every other node with in-degree 1, and everything reachable from the root. Check the degrees, then confirm reachability with one traversal.
Approach
- Compute the in-degree of every node from both child arrays. If any in-degree exceeds 1, return
false. - Find the nodes with in-degree 0. If there is not exactly one, return
false; call it the root. - BFS or DFS from the root along the child links, counting visited nodes.
- Return
trueexactly when allnnodes were visited.
Why it works
If every node has at most one parent and the root has none, the links form a forest of in-trees plus possibly cycles; a cycle's nodes all have a parent inside the cycle, so they are unreachable from the root. Reaching all n nodes from the single root therefore rules out cycles and extra components, leaving exactly one tree.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- A node can be its own child (
leftChild[i] == i) — in-degree and reachability still catch it. - Both children of a node may point to the same node; that node then has in-degree 2.
n = 1with no links is a valid one-node tree.
Reference solution
Python
from typing import List
def validateBinaryTreeNodes(n: int, leftChild: List[int], rightChild: List[int]) -> bool:
indeg = [0] * n
for c in leftChild + rightChild:
if c != -1:
indeg[c] += 1
if indeg[c] > 1:
return False
roots = [i for i in range(n) if indeg[i] == 0]
if len(roots) != 1:
return False
seen = [False] * n
seen[roots[0]] = True
stack = [roots[0]]
count = 1
while stack:
x = stack.pop()
for c in (leftChild[x], rightChild[x]):
if c != -1 and not seen[c]:
seen[c] = True
count += 1
stack.append(c)
return count == nJava
public static boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
int[] indeg = new int[n];
for (int i = 0; i < n; i++) {
if (leftChild[i] != -1 && ++indeg[leftChild[i]] > 1) return false;
if (rightChild[i] != -1 && ++indeg[rightChild[i]] > 1) return false;
}
int root = -1;
for (int i = 0; i < n; i++) {
if (indeg[i] != 0) continue;
if (root != -1) return false;
root = i;
}
if (root == -1) return false;
boolean[] seen = new boolean[n];
int[] stack = new int[n];
int top = 0, count = 1;
seen[root] = true;
stack[top++] = root;
while (top > 0) {
int x = stack[--top];
for (int c : new int[]{leftChild[x], rightChild[x]}) {
if (c != -1 && !seen[c]) { seen[c] = true; count++; stack[top++] = c; }
}
}
return count == n;
}C++
bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
vector<int> indeg(n, 0);
for (int i = 0; i < n; i++) {
if (leftChild[i] != -1 && ++indeg[leftChild[i]] > 1) return false;
if (rightChild[i] != -1 && ++indeg[rightChild[i]] > 1) return false;
}
int root = -1;
for (int i = 0; i < n; i++) {
if (indeg[i] != 0) continue;
if (root != -1) return false;
root = i;
}
if (root == -1) return false;
vector<bool> seen(n, false);
vector<int> st{root};
seen[root] = true;
int count = 1;
while (!st.empty()) {
int x = st.back(); st.pop_back();
for (int c : {leftChild[x], rightChild[x]}) {
if (c != -1 && !seen[c]) { seen[c] = true; count++; st.push_back(c); }
}
}
return count == n;
}JavaScript
var validateBinaryTreeNodes = function(n, leftChild, rightChild) {
var indeg = new Array(n).fill(0);
for (var i = 0; i < n; i++) {
var kids = [leftChild[i], rightChild[i]];
for (var k = 0; k < 2; k++) {
if (kids[k] === -1) continue;
if (++indeg[kids[k]] > 1) return false;
}
}
var root = -1;
for (var j = 0; j < n; j++) {
if (indeg[j] !== 0) continue;
if (root !== -1) return false;
root = j;
}
if (root === -1) return false;
var seen = new Array(n).fill(false), stack = [root], count = 1;
seen[root] = true;
while (stack.length) {
var x = stack.pop(), ch = [leftChild[x], rightChild[x]];
for (var t = 0; t < 2; t++) {
var c = ch[t];
if (c !== -1 && !seen[c]) { seen[c] = true; count++; stack.push(c); }
}
}
return count === n;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)