Validate Binary Tree Nodes

Medium
1696.

Validate Binary Tree Nodes

Validate Binary Tree Nodes is a medium coding problem on depth-first search, breadth-first search and trees, asked in Amazon and Meta interviews.

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.length
  • 1 <= n <= 10^4
  • -1 <= leftChild[i], rightChild[i] <= n - 1
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[]} leftChild
 * @param {number[]} rightChild
 * @return {boolean}
 */
var validateBinaryTreeNodes = function(n, leftChild, rightChild) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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.length
  • 1 <= n <= 10^4
  • -1 <= leftChild[i], rightChild[i] <= n - 1

Hints for Validate Binary Tree Nodes

  1. Hint 1

    In a valid tree exactly one node — the root — has no parent, and every other node has exactly one.

  2. Hint 2

    Count each node's parents. Any node with two parents fails immediately; zero or several parentless nodes fail too.

  3. Hint 3

    Parent counts alone miss a separate cycle (e.g. 1 → 2 → 1 beside a valid tree). From the unique root, traverse the children and check that all n nodes 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

  1. Compute the in-degree of every node from both child arrays. If any in-degree exceeds 1, return false.
  2. Find the nodes with in-degree 0. If there is not exactly one, return false; call it the root.
  3. BFS or DFS from the root along the child links, counting visited nodes.
  4. Return true exactly when all n nodes 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 = 1 with 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 == n

Java

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)