Scale Engineer

Validate Binary Tree Nodes

Med
#1263Time: O(N * α(N)), where N is the number of nodes and α is the Inverse Ackermann function. The main loop runs N times, and each union/find operation is nearly constant time.Space: O(N) to store the DSU's parent array and the in-degree array.
Algorithms
Depth-First SearchBreadth-First SearchUnion Find
Data structures
TreeBinary TreeGraph

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses a Union-Find (DSU) data structure to detect cycles and ensure all nodes form a single connected component. It also separately verifies the parent-child rules of a binary tree, namely that each node has at most one parent.

Algorithm

  • Initialize a Union-Find (DSU) data structure with n components, one for each node.
  • Initialize an inDegree array of size n to all zeros to track the number of parents for each node.
  • Iterate through each node p from 0 to n-1.
  • For each child c (leftChild[p] or rightChild[p]):
    • If c is not -1:
      • If c already has a parent (inDegree[c] == 1), it violates the binary tree property. Return false.
      • If p and c are already in the same connected component (find(p) == find(c)), adding the edge p -> c would create a cycle. Return false.
      • If the checks pass, increment inDegree[c] and perform union(p, c) to merge their sets.
  • After iterating through all nodes, we must have exactly one connected component and exactly one root.
  • The number of components in the DSU must be 1.
  • The number of nodes with an in-degree of 0 (roots) must be 1.
  • If both conditions hold, return true; otherwise, return false.

Walkthrough

A valid binary tree must be a single connected component, contain no cycles, and every node (except the root) must have exactly one parent. This approach tackles these conditions using a combination of an in-degree count and a DSU data structure.

  1. Parent Uniqueness: We use an inDegree array to track the number of parents for each node. As we process the leftChild and rightChild arrays, we check the child's in-degree. If a child node is about to be assigned a second parent, we immediately know the structure is invalid.

  2. Cycle Detection & Connectivity: A DSU data structure is initialized with n nodes, each in its own set. For each parent-child relationship p -> c, we first check for parent uniqueness. Then, we check if p and c are already in the same set using the find operation. If they are, it implies that an undirected path already exists between them. Since c has no other parent, this must mean c is an ancestor of p, so adding the edge p -> c would form a cycle. If no cycle is formed, we union them, merging their sets and decrementing the component count.

  3. Final Validation: After processing all edges, a valid tree must consist of a single component with a single root. We check that the final number of components in the DSU is 1 and that the number of nodes with an in-degree of 0 is also exactly 1.

class Solution {    class DSU {        private int[] parent;        private int components;         public DSU(int n) {            parent = new int[n];            components = n;            for (int i = 0; i < n; i++) {                parent[i] = i;            }        }         public int find(int i) {            if (parent[i] == i) {                return i;            }            return parent[i] = find(parent[i]);        }         public boolean union(int i, int j) {            int rootI = find(i);            int rootJ = find(j);            if (rootI != rootJ) {                parent[rootJ] = rootI;                components--;                return true;            }            return false;        }                public int getComponents() {            return components;        }    }     public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {        DSU dsu = new DSU(n);        int[] inDegree = new int[n];                for (int i = 0; i < n; i++) {            int lc = leftChild[i];            int rc = rightChild[i];             if (lc != -1) {                if (inDegree[lc] > 0) return false; // Already has a parent                if (dsu.find(i) == dsu.find(lc)) return false; // Cycle                dsu.union(i, lc);                inDegree[lc]++;            }             if (rc != -1) {                if (inDegree[rc] > 0) return false; // Already has a parent                if (dsu.find(i) == dsu.find(rc)) return false; // Cycle                dsu.union(i, rc);                inDegree[rc]++;            }        }         int rootCount = 0;        for (int i = 0; i < n; i++) {            if (inDegree[i] == 0) {                rootCount++;            }        }         return rootCount == 1 && dsu.getComponents() == 1;    }}

Complexity

Time

O(N * α(N)), where N is the number of nodes and α is the Inverse Ackermann function. The main loop runs N times, and each union/find operation is nearly constant time.

Space

O(N) to store the DSU's parent array and the in-degree array.

Trade-offs

Pros

  • Provides a structured way to check for connectivity and cycles simultaneously.

  • Union-Find is a standard, efficient data structure for problems involving disjoint sets.

Cons

  • More complex to implement correctly compared to a simple traversal.

  • The logic combines multiple concepts (in-degrees, DSU for cycles, DSU for components), making it less straightforward.

  • Can be slightly less performant in practice due to the overhead of the DSU data structure.

Solutions

class Solution {private  int[] p;public  boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {    p = new int[n];    for (int i = 0; i < n; ++i) {      p[i] = i;    }    boolean[] vis = new boolean[n];    for (int i = 0, m = n; i < m; ++i) {      for (int j : new int[]{leftChild[i], rightChild[i]}) {        if (j != -1) {          if (vis[j] || find(i) == find(j)) {            return false;          }          p[find(i)] = find(j);          vis[j] = true;          --n;        }      }    }    return n == 1;  }private  int find(int x) {    if (p[x] != x) {      p[x] = find(p[x]);    }    return p[x];  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem