Validate Binary Tree Nodes

Medium · Graphs · Explanation and code example

Disjoint Set Union

How it works

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.

Steps

  1. Initialize a DSU structure where each node is its own parent, with n separate components.
  2. For each parent node, attempt to union it with its left and right children.
  3. 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.
  4. If the union fails these checks, return false as it indicates multiple parents or a cycle.
  5. For each successful union, decrement the component count.
  6. After processing all edges, return true only if there is exactly one connected component.

Complexity

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

Things to watch for

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.

Python code example

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

C++ code example

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;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations