Validate Binary Tree Nodes: In-Degree + BFS

You are given n nodes numbered 0 to n-1, along with two arrays leftChild and rightChild. For each node i, leftChild[i] is the left child of node i (or -1 if none), and rightChild[i] is the right child (or -1). Determine whether these edges form exactly one valid binary tree.

This is LeetCode 1361: Validate Binary Tree Nodes, and it tests whether you can think about tree structure from the ground up rather than taking it for granted. Most tree problems hand you a root and say "traverse." This one hands you raw edges and says "prove this is actually a tree."

Why this problem matters

Binary tree problems usually assume the tree is already valid. You get a root pointer and start recursing. But what happens when the data itself might be broken? A node could have two parents. There could be a cycle. The nodes might form two disconnected components instead of one tree.

This problem forces you to articulate what makes a binary tree valid in the first place. A valid binary tree has exactly one root (a node with no parent), every other node has exactly one parent, and every node is reachable from the root. If any of those conditions fail, you do not have a tree. Once you break the problem into those three checks, the solution falls into place.

The key insight

Think about in-degrees. In a valid binary tree, the root has in-degree 0 (nothing points to it) and every other node has in-degree exactly 1 (exactly one parent). If you scan through leftChild and rightChild, you can count how many times each node appears as someone's child. That gives you the in-degree of every node.

From there, you need exactly one node with in-degree 0 (that is the root), and all other nodes must have in-degree 1. If a node has in-degree 2, it has two parents. If multiple nodes have in-degree 0, there are multiple roots, meaning disconnected components.

But in-degree checks alone are not enough. You could have a structure where the in-degrees are all correct but the nodes form a cycle that does not include the root. So after finding the root, you BFS from it and count how many nodes you reach. If you reach all n nodes, the structure is connected and acyclic. If not, something is disconnected or there is a cycle somewhere the root cannot reach.

The solution

from collections import deque

def validate_binary_tree_nodes(n, left_child, right_child):
    in_degree = [0] * n
    for i in range(n):
        if left_child[i] != -1:
            in_degree[left_child[i]] += 1
            if in_degree[left_child[i]] > 1:
                return False
        if right_child[i] != -1:
            in_degree[right_child[i]] += 1
            if in_degree[right_child[i]] > 1:
                return False

    root = -1
    for i in range(n):
        if in_degree[i] == 0:
            if root != -1:
                return False
            root = i

    if root == -1:
        return False

    queue = deque([root])
    visited = 0
    while queue:
        node = queue.popleft()
        visited += 1
        if left_child[node] != -1:
            queue.append(left_child[node])
        if right_child[node] != -1:
            queue.append(right_child[node])

    return visited == n

The solution has three clean phases. First, you build the in-degree array by scanning both child arrays. While counting, if any node's in-degree exceeds 1, you immediately know it has two parents, so you return False. Second, you find the root by looking for the unique node with in-degree 0. If there are zero roots or more than one, you return False. Third, you BFS from the root, counting how many nodes you visit. If the count equals n, every node is reachable from the root through the parent-child edges, and you have a valid tree.

Why does BFS with a visit count catch cycles? In a valid tree there are no cycles, so BFS visits each node at most once. If there were a cycle not reachable from the root, those nodes would never enter the queue, and the visit count would fall short of n.

Visual walkthrough

Complexity analysis

Time is O(n). You iterate through the child arrays once to build in-degrees (O(n)), scan the in-degree array once to find the root (O(n)), and BFS visits each node once (O(n)). Three linear passes.

Space is O(n). The in-degree array is size n, and the BFS queue can hold up to n nodes in the worst case (a tree that is one level deep with n-1 leaves).

The union-find approach also works. You process each edge by unioning parent and child. If a union would merge two nodes already in the same set, you have a cycle. At the end, check that there is exactly one connected component. The time is O(n * alpha(n)) where alpha is the inverse Ackermann function, which is effectively O(n) for all practical purposes.

The building blocks

1. In-degree analysis for root finding

In any directed tree, the root is the unique node with in-degree 0. This pattern shows up whenever you need to find the starting point in a directed graph with tree-like structure. You scan all edges, count how many times each node appears as a destination, and the node with zero incoming edges is the root. The same idea appears in topological sort: nodes with in-degree 0 are the ones with no prerequisites.

in_degree = [0] * n
for i in range(n):
    for child in [left_child[i], right_child[i]]:
        if child != -1:
            in_degree[child] += 1
root = [i for i in range(n) if in_degree[i] == 0]

2. BFS reachability check

Once you have a candidate root, BFS confirms connectivity. Start from the root, follow every edge, and count how many nodes you visit. If visited == n, the graph is connected from the root. If visited < n, some nodes are stranded in a separate component or trapped in a cycle the root cannot reach. This reachability check is a fundamental graph primitive that appears in problems like number of islands, course schedule, and clone graph.

Edge cases

• n = 1, no children: leftChild = [-1], rightChild = [-1]. Node 0 has in-degree 0, it is the root, BFS visits 1 node, and 1 == n. Return True.
• Two disconnected subtrees: For example, n=4 with nodes 0 and 2 each having in-degree 0. Two roots means two components. Return False at the root-finding step.
• A node is its own child: If leftChild[0] = 0, then node 0 has in-degree 1, so there would be no node with in-degree 0. Return False because no root exists.
• A cycle among non-root nodes: Suppose nodes 1 and 2 point to each other as children. Both would get in-degree 1, but BFS from the root would never reach the cycle. The visited count would be less than n.
• Single long chain: n=5 with each node pointing to the next as its left child. In-degrees are all 1 except the first node (in-degree 0). BFS visits all 5. This is a valid (skewed) binary tree.

From understanding to recall

You just traced through a solution that breaks tree validation into three phases: in-degree counting, root finding, and BFS reachability. Each phase answers a specific question. Does every node have at most one parent? Is there exactly one root? Are all nodes connected?

But here is the thing. In an interview, will you remember to check all three conditions? It is tempting to skip the BFS and just verify in-degrees, but that misses disconnected components. It is tempting to skip the in-degree check and just BFS from node 0, but that misses the case where node 0 is not the root.

Understanding is not the same as recall. You understood the three-phase approach. Recall means you can decompose the problem into those three checks from scratch, under pressure, without forgetting any of them.

Spaced repetition builds that recall. You practice reconstructing the in-degree scan, the root identification, and the BFS reachability check at increasing intervals. After a few reps, the decomposition is automatic. You see "validate tree structure" and your hands type the three-phase pattern without hesitation.

These building blocks, in-degree analysis and BFS reachability, show up across dozens of graph and tree problems. Drilling them individually means you are not just preparing for this one problem. You are building a toolkit that transfers to course scheduling, topological sorting, and connected component problems.

Related posts

• Validate Binary Search Tree - Another tree validation problem, but this one checks value ordering rather than structural validity
• Symmetric Tree - Validates a structural property (mirror symmetry) using recursive comparison
• Balanced Binary Tree - Bottom-up validation where you check a property (height balance) at every node during traversal
• Course Schedule - Uses in-degree analysis and BFS (topological sort) to detect cycles in a directed graph, the same core pattern as this problem

CodeBricks breaks problems like this into reusable building blocks, in-degree analysis and BFS reachability, and drills them with spaced repetition so you can recall the patterns cold. Instead of memorizing hundreds of solutions, you learn a small set of composable techniques that cover the majority of interview problems.