Watch 10 video solutions for Validate Binary Tree Nodes, a medium level problem involving Tree, Depth-First Search, Breadth-First Search. This walkthrough by codestorywithMIK has 12,563 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.length1 <= n <= 104-1 <= leftChild[i], rightChild[i] <= n - 1Problem Overview: You are given n nodes labeled 0..n-1 and two arrays leftChild and rightChild. Each index describes the left and right child of a node. The task is to verify whether these relationships form exactly one valid binary tree: one root, no node with multiple parents, no cycles, and all nodes connected.
The constraints make the problem easier to think about as a graph validation task rather than building an explicit tree. A valid binary tree must satisfy three properties: every node except the root has exactly one parent, there are no cycles, and all nodes belong to one connected component.
Approach 1: Disjoint Set Union (Union-Find) (O(n) time, O(n) space)
This method treats the structure as a directed graph and uses Union Find to detect cycles and multiple parents while connecting nodes. Iterate through each node and attempt to union it with its left and right children. If a child already belongs to the same set, a cycle exists. Maintain an array tracking whether a node already has a parent; if a second parent appears, the structure is invalid. After processing all edges, ensure exactly one connected component remains.
The key insight: a valid binary tree with n nodes must have exactly n-1 edges and remain fully connected without forming cycles. Union-Find efficiently enforces these conditions while processing edges once.
Approach 2: In-degree + Depth-First Search (DFS) (O(n) time, O(n) space)
This approach models the problem as a graph validation task using in-degree counting and traversal. First compute the in-degree of every node by scanning leftChild and rightChild. If any node reaches in-degree greater than 1, two parents exist and the structure cannot be a valid tree. The node with in-degree 0 must be the root; if there are zero or multiple such nodes, the tree is invalid.
Once the root is identified, run a Depth-First Search starting from that root. Track visited nodes while traversing left and right children. If DFS encounters a previously visited node, a cycle exists. After traversal, verify that all n nodes were visited, ensuring the structure is fully connected.
This approach mirrors how interviewers typically reason about trees: identify the root, enforce the single-parent rule with in-degree, then verify reachability with DFS.
Recommended for interviews: The in-degree + DFS approach is usually expected. It directly checks the defining properties of a tree: a single root, no node with multiple parents, and full connectivity. The Union-Find approach is also valid and shows strong understanding of graph cycle detection, which can stand out in system-heavy interviews.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Disjoint Set Union (Union-Find) | O(n) | O(n) | When treating the problem as graph connectivity with cycle detection |
| In-degree + DFS Traversal | O(n) | O(n) | Most intuitive interview solution for validating tree structure |