1361. Validate Binary Tree Nodes - Explanation

Description

There are n nodes labeled from 0 through n - 1. For each node i, leftChild[i] and rightChild[i] give the labels of its children. A child entry of -1 means that child is absent.

Return true exactly when these links form one valid binary tree containing all n nodes. Such a tree has one root with no parent, every other node has exactly one parent, and following child links from the root reaches every node without a cycle. Otherwise return false.

The root can have any label; it does not have to be node 0. The arrays describe links by node label, not level-order traversal or node values.

Edges labeled L and R identify left and right children.

Example 1:

Validate Binary Tree Nodes, example 1: illustration of the example

Input: n = 3
leftChild = [-1,-1,0]
rightChild = [-1,-1,1]

Output: true

Explanation: Node 2 is the root, with left child 0 and right child 1. Both children are leaves, and all three nodes belong to this one tree. A valid root need not have label 0.

Example 2:

Validate Binary Tree Nodes, example 2: illustration of the example

Input: n = 3
leftChild = [1,-1,-1]
rightChild = [2,2,-1]

Output: false

Explanation: Node 2 is listed as a child of both node 0 and node 1. A non-root node must have exactly one parent, so these links are invalid.

Example 3:

Validate Binary Tree Nodes, example 3: illustration of the example

Input: n = 3
leftChild = [1,0,-1]
rightChild = [-1,-1,-1]

Output: false

Explanation: Nodes 0 and 1 point to each other, forming a cycle. Node 2 is isolated. The links therefore do not form one tree containing all nodes.

Constraints:

1 <= n <= 10000
leftChild.length == rightChild.length == n
-1 <= leftChild[i], rightChild[i] < n

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Binary Tree Structure - Understanding parent-child relationships and what makes a valid binary tree
Depth First Search (DFS) - Recursive and iterative tree traversal to visit all nodes
Breadth First Search (BFS) - Level-order traversal using a queue
Indegree Counting - Tracking incoming edges to identify root nodes and detect multiple parents
Union-Find (Disjoint Set Union) - Detecting cycles and verifying connectivity in graph structures

1. Depth First Search

Intuition

A valid binary tree must have exactly one root (a node with no parent), every other node must have exactly one parent, and all nodes must be reachable from the root without cycles. The key insight is that we can identify the root as the only node that never appears as a child, then use DFS to verify that we can reach all n nodes without revisiting any node.

Algorithm

Build a set of all nodes that have a parent by collecting values from leftChild and rightChild arrays.
Find the root by identifying the node that is not in the hasParent set. If all nodes have parents, there is no root, so return false.
Perform dfs starting from the root, tracking visited nodes to detect cycles.
For each node, recursively visit its left and right children if they exist.
If we encounter a node that was already visited, a cycle exists, so return false.
After dfs completes, verify that we visited exactly n nodes to ensure all nodes are connected.

class Solution:
    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
        hasParent = set(leftChild + rightChild)
        hasParent.discard(-1)
        if len(hasParent) == n:
            return False

        root = -1
        for i in range(n):
            if i not in hasParent:
                root = i
                break

        visit = set()
        def dfs(i):
            if i == -1:
                return True
            if i in visit:
                return False
            visit.add(i)
            return dfs(leftChild[i]) and dfs(rightChild[i])

        return dfs(root) and len(visit) == n

public class Solution {
    private Set<Integer> visit;

    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        Set<Integer> hasParent = new HashSet<>();
        for (int c : leftChild) if (c != -1) hasParent.add(c);
        for (int c : rightChild) if (c != -1) hasParent.add(c);
        if (hasParent.size() == n) return false;

        int root = -1;
        for (int i = 0; i < n; i++) {
            if (!hasParent.contains(i)) {
                root = i;
                break;
            }
        }
        visit = new HashSet<>();
        return dfs(root, leftChild, rightChild) && visit.size() == n;
    }

    private boolean dfs(int i, int[] leftChild, int[] rightChild) {
        if (i == -1) return true;
        if (visit.contains(i)) return false;
        visit.add(i);
        return dfs(leftChild[i], leftChild, rightChild) &&
               dfs(rightChild[i], leftChild, rightChild);
    }
}

class Solution {
public:
    unordered_set<int> visit;

    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
        unordered_set<int> hasParent;
        for (int c : leftChild) if (c != -1) hasParent.insert(c);
        for (int c : rightChild) if (c != -1) hasParent.insert(c);
        if (hasParent.size() == n) return false;

        int root = -1;
        for (int i = 0; i < n; i++) {
            if (!hasParent.count(i)) {
                root = i;
                break;
            }
        }
        return dfs(root, leftChild, rightChild) && visit.size() == n;
    }

private:
    bool dfs(int i, vector<int>& leftChild, vector<int>& rightChild) {
        if (i == -1) return true;
        if (visit.count(i)) return false;
        visit.insert(i);
        return dfs(leftChild[i], leftChild, rightChild) &&
               dfs(rightChild[i], leftChild, rightChild);
    }
};

class Solution {
    /**
     * @param {number} n
     * @param {number[]} leftChild
     * @param {number[]} rightChild
     * @return {boolean}
     */
    validateBinaryTreeNodes(n, leftChild, rightChild) {
        let hasParent = new Set(
            [...leftChild, ...rightChild].filter((c) => c !== -1),
        );
        if (hasParent.size === n) return false;

        let root = 0;
        for (let i = 0; i < n; i++) {
            if (!hasParent.has(i)) {
                root = i;
                break;
            }
        }

        const visit = new Set();
        const dfs = (i) => {
            if (i === -1) return true;
            if (visit.has(i)) return false;
            visit.add(i);
            return dfs(leftChild[i]) && dfs(rightChild[i]);
        };

        return dfs(root) && visit.size === n;
    }
}

public class Solution {
    private HashSet<int> visit;

    public bool ValidateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        HashSet<int> hasParent = new HashSet<int>();
        foreach (int c in leftChild) if (c != -1) hasParent.Add(c);
        foreach (int c in rightChild) if (c != -1) hasParent.Add(c);
        if (hasParent.Count == n) return false;

        int root = -1;
        for (int i = 0; i < n; i++) {
            if (!hasParent.Contains(i)) {
                root = i;
                break;
            }
        }
        visit = new HashSet<int>();
        return Dfs(root, leftChild, rightChild) && visit.Count == n;
    }

    private bool Dfs(int i, int[] leftChild, int[] rightChild) {
        if (i == -1) return true;
        if (visit.Contains(i)) return false;
        visit.Add(i);
        return Dfs(leftChild[i], leftChild, rightChild) &&
               Dfs(rightChild[i], leftChild, rightChild);
    }
}

func validateBinaryTreeNodes(n int, leftChild []int, rightChild []int) bool {
    hasParent := make(map[int]bool)
    for _, c := range leftChild {
        if c != -1 {
            hasParent[c] = true
        }
    }
    for _, c := range rightChild {
        if c != -1 {
            hasParent[c] = true
        }
    }
    if len(hasParent) == n {
        return false
    }

    root := -1
    for i := 0; i < n; i++ {
        if !hasParent[i] {
            root = i
            break
        }
    }

    visit := make(map[int]bool)
    var dfs func(i int) bool
    dfs = func(i int) bool {
        if i == -1 {
            return true
        }
        if visit[i] {
            return false
        }
        visit[i] = true
        return dfs(leftChild[i]) && dfs(rightChild[i])
    }

    return dfs(root) && len(visit) == n
}

class Solution {
    private val visit = HashSet<Int>()

    fun validateBinaryTreeNodes(n: Int, leftChild: IntArray, rightChild: IntArray): Boolean {
        val hasParent = HashSet<Int>()
        for (c in leftChild) if (c != -1) hasParent.add(c)
        for (c in rightChild) if (c != -1) hasParent.add(c)
        if (hasParent.size == n) return false

        var root = -1
        for (i in 0 until n) {
            if (i !in hasParent) {
                root = i
                break
            }
        }
        visit.clear()
        return dfs(root, leftChild, rightChild) && visit.size == n
    }

    private fun dfs(i: Int, leftChild: IntArray, rightChild: IntArray): Boolean {
        if (i == -1) return true
        if (i in visit) return false
        visit.add(i)
        return dfs(leftChild[i], leftChild, rightChild) &&
               dfs(rightChild[i], leftChild, rightChild)
    }
}

class Solution {
    func validateBinaryTreeNodes(_ n: Int, _ leftChild: [Int], _ rightChild: [Int]) -> Bool {
        var hasParent = Set<Int>()
        for c in leftChild where c != -1 { hasParent.insert(c) }
        for c in rightChild where c != -1 { hasParent.insert(c) }
        if hasParent.count == n { return false }

        var root = -1
        for i in 0..<n {
            if !hasParent.contains(i) {
                root = i
                break
            }
        }

        var visit = Set<Int>()
        func dfs(_ i: Int) -> Bool {
            if i == -1 { return true }
            if visit.contains(i) { return false }
            visit.insert(i)
            return dfs(leftChild[i]) && dfs(rightChild[i])
        }

        return dfs(root) && visit.count == n
    }
}

impl Solution {
    pub fn validate_binary_tree_nodes(n: i32, left_child: Vec<i32>, right_child: Vec<i32>) -> bool {
        let n = n as usize;
        let mut has_parent = HashSet::new();
        for &c in left_child.iter().chain(right_child.iter()) {
            if c != -1 {
                has_parent.insert(c);
            }
        }
        if has_parent.len() == n {
            return false;
        }

        let mut root = -1i32;
        for i in 0..n as i32 {
            if !has_parent.contains(&i) {
                root = i;
                break;
            }
        }

        let mut visit = HashSet::new();
        fn dfs(
            i: i32,
            left_child: &[i32],
            right_child: &[i32],
            visit: &mut HashSet<i32>,
        ) -> bool {
            if i == -1 { return true; }
            if visit.contains(&i) { return false; }
            visit.insert(i);
            dfs(left_child[i as usize], left_child, right_child, visit)
                && dfs(right_child[i as usize], left_child, right_child, visit)
        }

        dfs(root, &left_child, &right_child, &mut visit) && visit.len() == n
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

2. Breadth First Search

Intuition

Instead of using recursion, we can use BFS to traverse the tree level by level. The approach uses indegree counting: in a valid binary tree, every node except the root has exactly one incoming edge (one parent). By tracking indegrees, we can detect nodes with multiple parents and identify the unique root.

Algorithm

Create an indegree array and count incoming edges for each node from both leftChild and rightChild arrays.
If any node has an indegree greater than 1 (multiple parents), return false immediately.
Find the root by locating the node with indegree == 0. If there are multiple such nodes or none, return false.
Perform bfs starting from the root using a queue, counting visited nodes.
For each node dequeued, add its valid children to the queue.
After bfs completes, return true only if the count of visited nodes equals n.

class Solution:
    def validateBinaryTreeNodes(self, n: int, leftChild: list[int], rightChild: list[int]) -> bool:
        indegree = [0] * n
        for i in range(n):
            if leftChild[i] != -1:
                indegree[leftChild[i]] += 1
                if indegree[leftChild[i]] > 1:
                    return False
            if rightChild[i] != -1:
                indegree[rightChild[i]] += 1
                if indegree[rightChild[i]] > 1:
                    return False

        root = -1
        for i in range(n):
            if indegree[i] == 0:
                if root != -1:
                    return False
                root = i

        if root == -1:
            return False

        count = 0
        q = deque([root])
        while q:
            i = q.popleft()
            count += 1
            if leftChild[i] != -1:
                q.append(leftChild[i])
            if rightChild[i] != -1:
                q.append(rightChild[i])
        return count == n

public class Solution {
    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        int[] indegree = new int[n];
        for (int i = 0; i < n; i++) {
            if (leftChild[i] != -1) {
                if (++indegree[leftChild[i]] > 1) return false;
            }
            if (rightChild[i] != -1) {
                if (++indegree[rightChild[i]] > 1) return false;
            }
        }

        int root = -1;
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                if (root != -1) return false;
                root = i;
            }
        }

        if (root == -1) return false;

        int count = 0;
        Queue<Integer> q = new LinkedList<>();
        q.offer(root);

        while (!q.isEmpty()) {
            int i = q.poll();
            count++;
            if (leftChild[i] != -1) q.offer(leftChild[i]);
            if (rightChild[i] != -1) q.offer(rightChild[i]);
        }
        return count == n;
    }
}

class Solution {
public:
    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
        vector<int> indegree(n, 0);
        for (int i = 0; i < n; i++) {
            if (leftChild[i] != -1) {
                if (++indegree[leftChild[i]] > 1) return false;
            }
            if (rightChild[i] != -1) {
                if (++indegree[rightChild[i]] > 1) return false;
            }
        }

        int root = -1;
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                if (root != -1) return false;
                root = i;
            }
        }

        if (root == -1) return false;

        int count = 0;
        queue<int> q;
        q.push(root);

        while (!q.empty()) {
            int i = q.front();q.pop();
            count++;
            if (leftChild[i] != -1) q.push(leftChild[i]);
            if (rightChild[i] != -1) q.push(rightChild[i]);
        }
        return count == n;
    }
};

class Solution {
    /**
     * @param {number} n
     * @param {number[]} leftChild
     * @param {number[]} rightChild
     * @return {boolean}
     */
    validateBinaryTreeNodes(n, leftChild, rightChild) {
        let indegree = new Array(n).fill(0);
        for (let i = 0; i < n; i++) {
            if (leftChild[i] !== -1) {
                if (++indegree[leftChild[i]] > 1) return false;
            }
            if (rightChild[i] !== -1) {
                if (++indegree[rightChild[i]] > 1) return false;
            }
        }

        let root = -1;
        for (let i = 0; i < n; i++) {
            if (indegree[i] === 0) {
                if (root !== -1) return false;
                root = i;
            }
        }

        if (root === -1) return false;

        let count = 0;
        let q = new Queue([root]);

        while (!q.isEmpty()) {
            let i = q.pop();
            count++;
            if (leftChild[i] !== -1) q.push(leftChild[i]);
            if (rightChild[i] !== -1) q.push(rightChild[i]);
        }
        return count === n;
    }
}

public class Solution {
    public bool ValidateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        int[] indegree = new int[n];
        for (int i = 0; i < n; i++) {
            if (leftChild[i] != -1) {
                if (++indegree[leftChild[i]] > 1) return false;
            }
            if (rightChild[i] != -1) {
                if (++indegree[rightChild[i]] > 1) return false;
            }
        }

        int root = -1;
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                if (root != -1) return false;
                root = i;
            }
        }

        if (root == -1) return false;

        int count = 0;
        Queue<int> q = new Queue<int>();
        q.Enqueue(root);

        while (q.Count > 0) {
            int node = q.Dequeue();
            count++;
            if (leftChild[node] != -1) q.Enqueue(leftChild[node]);
            if (rightChild[node] != -1) q.Enqueue(rightChild[node]);
        }
        return count == n;
    }
}

func validateBinaryTreeNodes(n int, leftChild []int, rightChild []int) bool {
    indegree := make([]int, n)
    for i := 0; i < n; i++ {
        if leftChild[i] != -1 {
            indegree[leftChild[i]]++
            if indegree[leftChild[i]] > 1 {
                return false
            }
        }
        if rightChild[i] != -1 {
            indegree[rightChild[i]]++
            if indegree[rightChild[i]] > 1 {
                return false
            }
        }
    }

    root := -1
    for i := 0; i < n; i++ {
        if indegree[i] == 0 {
            if root != -1 {
                return false
            }
            root = i
        }
    }

    if root == -1 {
        return false
    }

    count := 0
    q := []int{root}

    for len(q) > 0 {
        node := q[0]
        q = q[1:]
        count++
        if leftChild[node] != -1 {
            q = append(q, leftChild[node])
        }
        if rightChild[node] != -1 {
            q = append(q, rightChild[node])
        }
    }
    return count == n
}

class Solution {
    fun validateBinaryTreeNodes(n: Int, leftChild: IntArray, rightChild: IntArray): Boolean {
        val indegree = IntArray(n)
        for (i in 0 until n) {
            if (leftChild[i] != -1) {
                if (++indegree[leftChild[i]] > 1) return false
            }
            if (rightChild[i] != -1) {
                if (++indegree[rightChild[i]] > 1) return false
            }
        }

        var root = -1
        for (i in 0 until n) {
            if (indegree[i] == 0) {
                if (root != -1) return false
                root = i
            }
        }

        if (root == -1) return false

        var count = 0
        val q: Queue<Int> = LinkedList()
        q.offer(root)

        while (q.isNotEmpty()) {
            val node = q.poll()
            count++
            if (leftChild[node] != -1) q.offer(leftChild[node])
            if (rightChild[node] != -1) q.offer(rightChild[node])
        }
        return count == n
    }
}

class Solution {
    func validateBinaryTreeNodes(_ n: Int, _ leftChild: [Int], _ rightChild: [Int]) -> Bool {
        var indegree = [Int](repeating: 0, count: n)
        for i in 0..<n {
            if leftChild[i] != -1 {
                indegree[leftChild[i]] += 1
                if indegree[leftChild[i]] > 1 { return false }
            }
            if rightChild[i] != -1 {
                indegree[rightChild[i]] += 1
                if indegree[rightChild[i]] > 1 { return false }
            }
        }

        var root = -1
        for i in 0..<n {
            if indegree[i] == 0 {
                if root != -1 { return false }
                root = i
            }
        }

        if root == -1 { return false }

        var count = 0
        var q = [root]

        while !q.isEmpty {
            let node = q.removeFirst()
            count += 1
            if leftChild[node] != -1 { q.append(leftChild[node]) }
            if rightChild[node] != -1 { q.append(rightChild[node]) }
        }
        return count == n
    }
}

impl Solution {
    pub fn validate_binary_tree_nodes(n: i32, left_child: Vec<i32>, right_child: Vec<i32>) -> bool {
        let n = n as usize;
        let mut indegree = vec![0i32; n];
        for i in 0..n {
            if left_child[i] != -1 {
                indegree[left_child[i] as usize] += 1;
                if indegree[left_child[i] as usize] > 1 { return false; }
            }
            if right_child[i] != -1 {
                indegree[right_child[i] as usize] += 1;
                if indegree[right_child[i] as usize] > 1 { return false; }
            }
        }

        let mut root = -1i32;
        for i in 0..n {
            if indegree[i] == 0 {
                if root != -1 { return false; }
                root = i as i32;
            }
        }

        if root == -1 { return false; }

        let mut count = 0;
        let mut q = VecDeque::new();
        q.push_back(root);

        while let Some(node) = q.pop_front() {
            count += 1;
            let node = node as usize;
            if left_child[node] != -1 { q.push_back(left_child[node]); }
            if right_child[node] != -1 { q.push_back(right_child[node]); }
        }
        count == n
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Iterative DFS

Intuition

This approach combines the indegree validation from BFS with an iterative stack-based traversal instead of recursion. Using a stack avoids potential stack overflow issues for deep trees while maintaining the same logical flow as recursive DFS.

Algorithm

Create an indegree array and count incoming edges for each node.
Return false if any node has more than one parent.
Find the unique root node with indegree == 0. Return false if no root exists or multiple roots exist.
Initialize a stack with the root node and a counter for visited nodes.
Pop nodes from the stack, increment the counter, and push valid children onto the stack.
After the stack is empty, verify that the count equals n to confirm all nodes are reachable.

class Solution:
    def validateBinaryTreeNodes(self, n: int, leftChild: list[int], rightChild: list[int]) -> bool:
        indegree = [0] * n
        for i in range(n):
            if leftChild[i] != -1:
                indegree[leftChild[i]] += 1
                if indegree[leftChild[i]] > 1:
                    return False
            if rightChild[i] != -1:
                indegree[rightChild[i]] += 1
                if indegree[rightChild[i]] > 1:
                    return False

        root = next((i for i in range(n) if indegree[i] == 0), -1)
        if root == -1:
            return False

        count, stack = 0, [root]
        while stack:
            node = stack.pop()
            count += 1
            if leftChild[node] != -1:
                stack.append(leftChild[node])
            if rightChild[node] != -1:
                stack.append(rightChild[node])

        return count == n

public class Solution {
    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        int[] indegree = new int[n];
        for (int i = 0; i < n; i++) {
            if (leftChild[i] != -1) {
                if (++indegree[leftChild[i]] > 1) return false;
            }
            if (rightChild[i] != -1) {
                if (++indegree[rightChild[i]] > 1) return false;
            }
        }

        int root = -1;
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                if (root != -1) return false;
                root = i;
            }
        }

        if (root == -1) return false;

        int count = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            int node = stack.pop();
            count++;
            if (leftChild[node] != -1) stack.push(leftChild[node]);
            if (rightChild[node] != -1) stack.push(rightChild[node]);
        }
        return count == n;
    }
}

class Solution {
public:
    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
        vector<int> indegree(n, 0);
        for (int i = 0; i < n; i++) {
            if (leftChild[i] != -1 && ++indegree[leftChild[i]] > 1) return false;
            if (rightChild[i] != -1 && ++indegree[rightChild[i]] > 1) return false;
        }

        int root = -1;
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                if (root != -1) return false;
                root = i;
            }
        }

        if (root == -1) return false;

        int count = 0;
        stack<int> stk;
        stk.push(root);

        while (!stk.empty()) {
            int node = stk.top(); stk.pop();
            count++;
            if (leftChild[node] != -1) stk.push(leftChild[node]);
            if (rightChild[node] != -1) stk.push(rightChild[node]);
        }
        return count == n;
    }
};

class Solution {
    /**
     * @param {number} n
     * @param {number[]} leftChild
     * @param {number[]} rightChild
     * @return {boolean}
     */
    validateBinaryTreeNodes(n, leftChild, rightChild) {
        let indegree = new Array(n).fill(0);
        for (let i = 0; i < n; i++) {
            if (leftChild[i] !== -1) {
                if (++indegree[leftChild[i]] > 1) return false;
            }
            if (rightChild[i] !== -1) {
                if (++indegree[rightChild[i]] > 1) return false;
            }
        }

        let root = -1;
        for (let i = 0; i < n; i++) {
            if (indegree[i] === 0) {
                if (root !== -1) return false;
                root = i;
            }
        }

        if (root === -1) return false;

        let count = 0;
        let stack = [root];

        while (stack.length) {
            let node = stack.pop();
            count++;
            if (leftChild[node] !== -1) stack.push(leftChild[node]);
            if (rightChild[node] !== -1) stack.push(rightChild[node]);
        }
        return count === n;
    }
}

public class Solution {
    public bool ValidateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        int[] indegree = new int[n];
        for (int i = 0; i < n; i++) {
            if (leftChild[i] != -1) {
                if (++indegree[leftChild[i]] > 1) return false;
            }
            if (rightChild[i] != -1) {
                if (++indegree[rightChild[i]] > 1) return false;
            }
        }

        int root = -1;
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                if (root != -1) return false;
                root = i;
            }
        }

        if (root == -1) return false;

        int count = 0;
        Stack<int> stack = new Stack<int>();
        stack.Push(root);

        while (stack.Count > 0) {
            int node = stack.Pop();
            count++;
            if (leftChild[node] != -1) stack.Push(leftChild[node]);
            if (rightChild[node] != -1) stack.Push(rightChild[node]);
        }
        return count == n;
    }
}

func validateBinaryTreeNodes(n int, leftChild []int, rightChild []int) bool {
    indegree := make([]int, n)
    for i := 0; i < n; i++ {
        if leftChild[i] != -1 {
            indegree[leftChild[i]]++
            if indegree[leftChild[i]] > 1 {
                return false
            }
        }
        if rightChild[i] != -1 {
            indegree[rightChild[i]]++
            if indegree[rightChild[i]] > 1 {
                return false
            }
        }
    }

    root := -1
    for i := 0; i < n; i++ {
        if indegree[i] == 0 {
            if root != -1 {
                return false
            }
            root = i
        }
    }

    if root == -1 {
        return false
    }

    count := 0
    stack := []int{root}

    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        count++
        if leftChild[node] != -1 {
            stack = append(stack, leftChild[node])
        }
        if rightChild[node] != -1 {
            stack = append(stack, rightChild[node])
        }
    }
    return count == n
}

class Solution {
    fun validateBinaryTreeNodes(n: Int, leftChild: IntArray, rightChild: IntArray): Boolean {
        val indegree = IntArray(n)
        for (i in 0 until n) {
            if (leftChild[i] != -1) {
                if (++indegree[leftChild[i]] > 1) return false
            }
            if (rightChild[i] != -1) {
                if (++indegree[rightChild[i]] > 1) return false
            }
        }

        var root = -1
        for (i in 0 until n) {
            if (indegree[i] == 0) {
                if (root != -1) return false
                root = i
            }
        }

        if (root == -1) return false

        var count = 0
        val stack = ArrayDeque<Int>()
        stack.addLast(root)

        while (stack.isNotEmpty()) {
            val node = stack.removeLast()
            count++
            if (leftChild[node] != -1) stack.addLast(leftChild[node])
            if (rightChild[node] != -1) stack.addLast(rightChild[node])
        }
        return count == n
    }
}

class Solution {
    func validateBinaryTreeNodes(_ n: Int, _ leftChild: [Int], _ rightChild: [Int]) -> Bool {
        var indegree = [Int](repeating: 0, count: n)
        for i in 0..<n {
            if leftChild[i] != -1 {
                indegree[leftChild[i]] += 1
                if indegree[leftChild[i]] > 1 { return false }
            }
            if rightChild[i] != -1 {
                indegree[rightChild[i]] += 1
                if indegree[rightChild[i]] > 1 { return false }
            }
        }

        var root = -1
        for i in 0..<n {
            if indegree[i] == 0 {
                if root != -1 { return false }
                root = i
            }
        }

        if root == -1 { return false }

        var count = 0
        var stack = [root]

        while !stack.isEmpty {
            let node = stack.removeLast()
            count += 1
            if leftChild[node] != -1 { stack.append(leftChild[node]) }
            if rightChild[node] != -1 { stack.append(rightChild[node]) }
        }
        return count == n
    }
}

impl Solution {
    pub fn validate_binary_tree_nodes(n: i32, left_child: Vec<i32>, right_child: Vec<i32>) -> bool {
        let n = n as usize;
        let mut indegree = vec![0i32; n];
        for i in 0..n {
            if left_child[i] != -1 {
                indegree[left_child[i] as usize] += 1;
                if indegree[left_child[i] as usize] > 1 { return false; }
            }
            if right_child[i] != -1 {
                indegree[right_child[i] as usize] += 1;
                if indegree[right_child[i] as usize] > 1 { return false; }
            }
        }

        let mut root = -1i32;
        for i in 0..n {
            if indegree[i] == 0 {
                if root != -1 { return false; }
                root = i as i32;
            }
        }

        if root == -1 { return false; }

        let mut count = 0;
        let mut stack = vec![root];

        while let Some(node) = stack.pop() {
            count += 1;
            let node = node as usize;
            if left_child[node] != -1 { stack.push(left_child[node]); }
            if right_child[node] != -1 { stack.push(right_child[node]); }
        }
        count == n
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Disjoint Set Union

Intuition

Union-Find provides an elegant way to detect cycles and verify connectivity. The key insight is that in a valid tree, connecting a parent to a child should always merge two separate components. If the child already has a parent (its root is not itself) or connecting them would create a cycle (same root), the structure is invalid.

Algorithm

Initialize a DSU structure where each node is its own parent, with n separate components.
For each parent node, attempt to union it with its left and right children.
During union, check that the child's root equals itself (meaning it has no parent yet) and that the parent and child are not already in the same component.
If the union fails these checks, return false as it indicates multiple parents or a cycle.
For each successful union, decrement the component count.
After processing all edges, return true only if there is exactly one connected component.

class DSU:
    def __init__(self, n):
        self.Parent = list(range(n))
        self.Components = n

    def find(self, node):
        if self.Parent[node] != node:
            self.Parent[node] = self.find(self.Parent[node])
        return self.Parent[node]

    def union(self, parent, child):
        parentRoot = self.find(parent)
        childRoot = self.find(child)
        if childRoot != child or parentRoot == childRoot:
            return False

        self.Components -= 1
        self.Parent[childRoot] = parentRoot
        return True

class Solution:
    def validateBinaryTreeNodes(self, n: int, leftChild: list[int], rightChild: list[int]) -> bool:
        dsu = DSU(n)

        for parent in range(n):
            for child in (leftChild[parent], rightChild[parent]):
                if child == -1:
                    continue
                if not dsu.union(parent, child):
                    return False

        return dsu.Components == 1

class DSU {
    int[] Parent;
    int Components;

    public DSU(int n) {
        Parent = new int[n];
        for (int i = 0; i < n; i++) {
            Parent[i] = i;
        }
        Components = n;
    }

    public int find(int node) {
        if (Parent[node] != node) {
            Parent[node] = find(Parent[node]);
        }
        return Parent[node];
    }

    public boolean union(int parent, int child) {
        int parentRoot = find(parent);
        int childRoot = find(child);
        if (childRoot != child || parentRoot == childRoot) {
            return false;
        }

        Components--;
        Parent[childRoot] = parentRoot;
        return true;
    }
}

class Solution {
    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        DSU dsu = new DSU(n);

        for (int parent = 0; parent < n; parent++) {
            for (int child : new int[]{leftChild[parent], rightChild[parent]}) {
                if (child == -1) continue;
                if (!dsu.union(parent, child)) return false;
            }
        }

        return dsu.Components == 1;
    }
}

class DSU {
public:
    vector<int> Parent;
    int Components;

    DSU(int n) {
        Parent.resize(n);
        iota(Parent.begin(), Parent.end(), 0);
        Components = n;
    }

    int find(int node) {
        if (Parent[node] != node) {
            Parent[node] = find(Parent[node]);
        }
        return Parent[node];
    }

    bool unionSets(int parent, int child) {
        int parentRoot = find(parent);
        int childRoot = find(child);
        if (childRoot != child || parentRoot == childRoot) {
            return false;
        }

        Components--;
        Parent[childRoot] = parentRoot;
        return true;
    }
};

class Solution {
public:
    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
        DSU dsu(n);

        for (int parent = 0; parent < n; parent++) {
            for (int child : {leftChild[parent], rightChild[parent]}) {
                if (child == -1) continue;
                if (!dsu.unionSets(parent, child)) return false;
            }
        }

        return dsu.Components == 1;
    }
};

class DSU {
    /**
     * @constructor
     * @param {number} n
     */
    constructor(n) {
        this.Parent = Array.from({ length: n }, (_, i) => i);
        this.Components = n;
    }

    /**
     * @param {number} node
     * @return {number}
     */
    find(node) {
        if (this.Parent[node] !== node) {
            this.Parent[node] = this.find(this.Parent[node]);
        }
        return this.Parent[node];
    }

    /**
     * @param {number} parent
     * @param {number} child
     * @return {boolean}
     */
    union(parent, child) {
        let parentRoot = this.find(parent);
        let childRoot = this.find(child);
        if (childRoot !== child || parentRoot === childRoot) {
            return false;
        }

        this.Components--;
        this.Parent[childRoot] = parentRoot;
        return true;
    }
}

class Solution {
    /**
     * @param {number} n
     * @param {number[]} leftChild
     * @param {number[]} rightChild
     * @return {boolean}
     */
    validateBinaryTreeNodes(n, leftChild, rightChild) {
        let dsu = new DSU(n);

        for (let parent = 0; parent < n; parent++) {
            for (let child of [leftChild[parent], rightChild[parent]]) {
                if (child === -1) continue;
                if (!dsu.union(parent, child)) return false;
            }
        }

        return dsu.Components === 1;
    }
}

public class DSU {
    private int[] Parent;
    public int Components;

    public DSU(int n) {
        Parent = new int[n];
        for (int i = 0; i < n; i++) {
            Parent[i] = i;
        }
        Components = n;
    }

    public int Find(int node) {
        if (Parent[node] != node) {
            Parent[node] = Find(Parent[node]);
        }
        return Parent[node];
    }

    public bool Union(int parent, int child) {
        int parentRoot = Find(parent);
        int childRoot = Find(child);
        if (childRoot != child || parentRoot == childRoot) {
            return false;
        }

        Components--;
        Parent[childRoot] = parentRoot;
        return true;
    }
}

public class Solution {
    public bool ValidateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        DSU dsu = new DSU(n);

        for (int parent = 0; parent < n; parent++) {
            foreach (int child in new int[] { leftChild[parent], rightChild[parent] }) {
                if (child == -1) continue;
                if (!dsu.Union(parent, child)) return false;
            }
        }

        return dsu.Components == 1;
    }
}

type DSU struct {
    Parent     []int
    Components int
}

func NewDSU(n int) *DSU {
    parent := make([]int, n)
    for i := 0; i < n; i++ {
        parent[i] = i
    }
    return &DSU{Parent: parent, Components: n}
}

func (dsu *DSU) Find(node int) int {
    if dsu.Parent[node] != node {
        dsu.Parent[node] = dsu.Find(dsu.Parent[node])
    }
    return dsu.Parent[node]
}

func (dsu *DSU) Union(parent, child int) bool {
    parentRoot := dsu.Find(parent)
    childRoot := dsu.Find(child)
    if childRoot != child || parentRoot == childRoot {
        return false
    }

    dsu.Components--
    dsu.Parent[childRoot] = parentRoot
    return true
}

func validateBinaryTreeNodes(n int, leftChild []int, rightChild []int) bool {
    dsu := NewDSU(n)

    for parent := 0; parent < n; parent++ {
        for _, child := range []int{leftChild[parent], rightChild[parent]} {
            if child == -1 {
                continue
            }
            if !dsu.Union(parent, child) {
                return false
            }
        }
    }

    return dsu.Components == 1
}

class DSU(n: Int) {
    private val parent = IntArray(n) { it }
    var components = n
        private set

    fun find(node: Int): Int {
        if (parent[node] != node) {
            parent[node] = find(parent[node])
        }
        return parent[node]
    }

    fun union(parentNode: Int, child: Int): Boolean {
        val parentRoot = find(parentNode)
        val childRoot = find(child)
        if (childRoot != child || parentRoot == childRoot) {
            return false
        }

        components--
        parent[childRoot] = parentRoot
        return true
    }
}

class Solution {
    fun validateBinaryTreeNodes(n: Int, leftChild: IntArray, rightChild: IntArray): Boolean {
        val dsu = DSU(n)

        for (parent in 0 until n) {
            for (child in listOf(leftChild[parent], rightChild[parent])) {
                if (child == -1) continue
                if (!dsu.union(parent, child)) return false
            }
        }

        return dsu.components == 1
    }
}

class DSU {
    var parent: [Int]
    var components: Int

    init(_ n: Int) {
        parent = Array(0..<n)
        components = n
    }

    func find(_ node: Int) -> Int {
        if parent[node] != node {
            parent[node] = find(parent[node])
        }
        return parent[node]
    }

    func union(_ parentNode: Int, _ child: Int) -> Bool {
        let parentRoot = find(parentNode)
        let childRoot = find(child)
        if childRoot != child || parentRoot == childRoot {
            return false
        }

        components -= 1
        parent[childRoot] = parentRoot
        return true
    }
}

class Solution {
    func validateBinaryTreeNodes(_ n: Int, _ leftChild: [Int], _ rightChild: [Int]) -> Bool {
        let dsu = DSU(n)

        for parent in 0..<n {
            for child in [leftChild[parent], rightChild[parent]] {
                if child == -1 { continue }
                if !dsu.union(parent, child) { return false }
            }
        }

        return dsu.components == 1
    }
}

struct DSU {
    parent: Vec<usize>,
    components: usize,
}

impl DSU {
    fn new(n: usize) -> Self {
        Self {
            parent: (0..n).collect(),
            components: n,
        }
    }

    fn find(&mut self, node: usize) -> usize {
        if self.parent[node] != node {
            self.parent[node] = self.find(self.parent[node]);
        }
        self.parent[node]
    }

    fn union(&mut self, parent: usize, child: usize) -> bool {
        let parent_root = self.find(parent);
        let child_root = self.find(child);
        if child_root != child || parent_root == child_root {
            return false;
        }
        self.components -= 1;
        self.parent[child_root] = parent_root;
        true
    }
}

impl Solution {
    pub fn validate_binary_tree_nodes(n: i32, left_child: Vec<i32>, right_child: Vec<i32>) -> bool {
        let n = n as usize;
        let mut dsu = DSU::new(n);

        for p in 0..n {
            for &child in &[left_child[p], right_child[p]] {
                if child == -1 { continue; }
                if !dsu.union(p, child as usize) { return false; }
            }
        }

        dsu.components == 1
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

Common Pitfalls

Assuming Node 0 Is Always the Root

A common mistake is assuming node 0 is always the root of the tree. The root is the node with no incoming edges (no parent), which could be any node from 0 to n-1. You must explicitly find the root by identifying which node never appears in leftChild or rightChild arrays.

Forgetting to Check for Multiple Roots

A valid binary tree has exactly one root. If multiple nodes have no parent (indegree of 0), the structure is a forest, not a single tree. Always verify that exactly one node qualifies as the root before proceeding with traversal.

Not Verifying All Nodes Are Reachable

Even if you find a valid root and detect no cycles, you must confirm that all n nodes are reachable from the root. Disconnected components would mean some nodes are not part of the tree rooted at the identified root. After traversal, verify the count of visited nodes equals n.