# Validate Binary Tree Nodes
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/validate-binary-tree-nodes)
Canonical: https://scaleengineer.com/dsa/problems/validate-binary-tree-nodes
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Tree, Binary Tree, Graph
---
## Problem
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:**

![](https://assets.glich.co/dsa/validate-binary-tree-nodes/image0.png) 

**Input:** n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
**Output:** true

**Example 2:**

![](https://assets.glich.co/dsa/validate-binary-tree-nodes/image1.png) 

**Input:** n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1]
**Output:** false

**Example 3:**

![](https://assets.glich.co/dsa/validate-binary-tree-nodes/image2.png) 

**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
## Union-Find (Disjoint Set Union)
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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`.

## Graph Traversal (BFS/DFS) with In-Degree Check
This is a more direct and efficient approach. It first identifies a single potential root node by checking the in-degrees of all nodes. Then, it performs a single graph traversal (like Breadth-First Search) starting from that root to ensure all nodes are reachable and form a single connected component. This series of checks holistically validates the structure as a single binary tree.
**Time:** O(N), where N is the number of nodes. Calculating in-degrees takes O(N), finding the root takes O(N), and the BFS/DFS traversal visits each node and edge once, which is also O(N). · **Space:** O(N) to store the in-degree array, the queue for BFS, and the visited array.
**Pros:** Highly efficient with linear time and space complexity.; Conceptually straightforward, breaking the problem down into clear, verifiable properties.; Robust and less prone to subtle implementation errors compared to DSU on directed graphs.
**Cons:** Requires multiple passes over the data (one for in-degrees, one for traversal), though this does not affect the overall asymptotic complexity.
### Explanation
A valid binary tree has key properties that we can check sequentially for an elegant and efficient solution:

1.  **Single Parent & Single Root Rule**: A binary tree must have exactly one root (a node with no parent), and every other node must have exactly one parent. We can verify this by computing the in-degree for every node. We iterate through all parent-child connections, build an `inDegree` array, and then scan this array. If we find any node with an in-degree greater than 1, or if we don't find exactly one node with an in-degree of 0, the structure is invalid.

2.  **Connectivity & Acyclicity**: If the parent/root rules hold, the graph consists of one or more components, each of which is a tree. To be a single valid binary tree, all `n` nodes must belong to the component of the single root we identified. We can verify this by starting a traversal (BFS or DFS) from the root. By counting the nodes visited, we can determine if the graph is fully connected. If the traversal visits exactly `n` nodes, then all nodes are reachable from the single root, forming one connected component. This also implicitly confirms there are no cycles, as a cycle would have violated the in-degree rules.

This leads to a clean, multi-step algorithm that is easy to implement and understand.

```java
import java.util.Queue;
import java.util.LinkedList;

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) {
                inDegree[leftChild[i]]++;
            }
            if (rightChild[i] != -1) {
                inDegree[rightChild[i]]++;
            }
        }

        int root = -1;
        for (int i = 0; i < n; i++) {
            if (inDegree[i] > 1) {
                return false; // Node with more than one parent
            }
            if (inDegree[i] == 0) {
                if (root != -1) {
                    return false; // More than one root
                }
                root = i;
            }
        }

        if (root == -1) {
            return false; // No root found (e.g., a cycle)
        }

        // BFS to check connectivity and count visited nodes
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[n];
        int visitedCount = 0;

        queue.offer(root);
        visited[root] = true;
        visitedCount++;

        while (!queue.isEmpty()) {
            int u = queue.poll();

            int lc = leftChild[u];
            if (lc != -1) {
                // This check is technically redundant if in-degree checks passed,
                // but provides extra safety.
                if (visited[lc]) return false; 
                visited[lc] = true;
                queue.offer(lc);
                visitedCount++;
            }

            int rc = rightChild[u];
            if (rc != -1) {
                if (visited[rc]) return false;
                visited[rc] = true;
                queue.offer(rc);
                visitedCount++;
            }
        }

        return visitedCount == n;
    }
}
```
### Algorithm
- Create an `inDegree` array of size `n` and initialize it to all zeros.
- Populate the `inDegree` array by iterating through `leftChild` and `rightChild` arrays. For each valid child, increment its in-degree.
- Find the root of the potential tree. Iterate through the `inDegree` array:
  - A node `i` is a potential root if `inDegree[i] == 0`.
  - If there is not exactly one node with an in-degree of 0, return `false`.
  - If any node has an in-degree greater than 1, return `false`.
- If a unique root is found, perform a graph traversal (BFS or DFS) starting from that root.
- Keep a count of the number of nodes visited during the traversal.
- After the traversal, if the number of visited nodes is equal to `n`, it means all nodes are connected in a single component. Return `true`.
- Otherwise, the graph is disconnected (a forest), so return `false`.

# Solutions
### Java

```java
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];
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool validateBinaryTreeNodes(int n, vector<int> &leftChild,
                               vector<int> &rightChild) {
    int p[n];
    iota(p, p + n, 0);
    bool vis[n];
    memset(vis, 0, sizeof(vis));
    function<int(int)> find = [&](int x) {
      return p[x] == x ? x : p[x] = find(p[x]);
    };
    for (int i = 0, m = n; i < m; ++i) {
      for (int j : {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;
  }
};

```

### Python

```python
class Solution:
    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool: def find(x: int) -> int: if p[x] != x: p[x] = find(p[x]) return p[x] p = list(range(n)) vis = [False] * n for i, (a, b) in enumerate(zip(leftChild, rightChild)): for j in (a, b): if j != - 1: if vis[j] or find(i) == find(j): return False p[find(i)] = find(j) vis[j] = True n -= 1 return n == 1

```