1361. Validate Binary Tree Nodes - Explanation

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

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

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

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

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.