LeetCode 1361 - Validate Binary Tree Nodes

LeetCode Problem 1361

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Breadth-First Search, Union-Find, Graph Theory, Binary Tree

Solution

Problem Understanding

The problem gives us n nodes labeled from 0 to n - 1. For every node i, we are told which node is its left child and which node is its right child through the arrays leftChild and rightChild.

If leftChild[i] = x, then node x is the left child of node i. Similarly, if rightChild[i] = y, then node y is the right child of node i. A value of -1 means that the child does not exist.

We must determine whether all nodes together form exactly one valid binary tree.

A valid binary tree must satisfy several conditions simultaneously:

There must be exactly one root node.
Every node except the root must have exactly one parent.
The structure must be connected, meaning every node is reachable from the root.
The structure must not contain cycles.

The input does not explicitly provide the root. We must infer it from the parent-child relationships.

The constraints are important:

n can be as large as 10^4
Each node has at most two outgoing edges
Child values are either -1 or valid node indices

Since n is fairly large, an O(n^2) solution is undesirable. We should aim for a linear or near-linear algorithm.

Several edge cases can easily break naive implementations:

A node may have two parents.
Multiple disconnected components may exist.
A cycle may exist.
There may be multiple roots.
There may be no root at all.
A single-node tree should still be considered valid.

The key challenge is recognizing that all four validity conditions must hold simultaneously.

Approaches

Brute Force Approach

A brute-force strategy would attempt to validate the tree by checking every node independently.

One possible brute-force method is:

Treat each node as a possible root.
Run DFS or BFS from that node.
Check whether all nodes are visited exactly once.
Verify there are no cycles.
Verify no node has multiple parents.

This works because a valid binary tree must have exactly one node from which all others are reachable without revisiting any node.

However, this approach is inefficient because we may run a traversal from every node. Each traversal costs O(n), leading to a worst-case complexity of O(n^2).

With n = 10^4, quadratic complexity is unnecessarily expensive.

Optimal Approach

The key insight is that a valid binary tree has very strict structural properties:

Exactly one node has indegree 0, this is the root.
Every other node has indegree 1.
No node can have indegree greater than 1.
Starting from the root, we must visit every node exactly once.

Instead of testing every node as a root, we can compute indegrees directly.

We first process all child relationships:

If any node receives two parents, the structure is invalid immediately.
After processing all edges, exactly one node must have indegree 0.

Once we identify the root, we perform a DFS or BFS:

If we encounter a node twice, a cycle exists.
If not all nodes are visited, the graph is disconnected.

This gives a clean linear-time solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Runs traversal from every possible root
Optimal	O(n)	O(n)	Uses indegree analysis plus one traversal

Algorithm Walkthrough

Create an indegree array of size n, initialized to 0.

The indegree of a node represents how many parents it has. In a valid binary tree, every node except the root must have exactly one parent. 2. Iterate through every node and process its left and right children.

For each valid child:

Increment that child's indegree.
If the indegree becomes greater than 1, immediately return False.

This step ensures no node has multiple parents. 3. Find the root node.

The root is the only node whose indegree remains 0.

While scanning the indegree array:

Count how many nodes have indegree 0.
If the count is not exactly 1, return False.

Multiple roots imply disconnected components. No roots imply a cycle. 4. Perform DFS or BFS starting from the root.

Use a visited set to track nodes already seen.

During traversal:

If a node is encountered twice, a cycle exists, return False.
Otherwise, continue traversing its children.

After traversal completes, verify connectivity.

If the number of visited nodes is not equal to n, some nodes were unreachable from the root.

In that case, return False. 6. If all checks pass, return True.

Why it works

The algorithm enforces every structural requirement of a binary tree.

The indegree check guarantees that every node has at most one parent and that exactly one root exists. The DFS traversal guarantees there are no cycles and that the graph is fully connected. Since all required properties are validated, the structure must be exactly one valid binary tree.

Python Solution

from typing import List

class Solution:
    def validateBinaryTreeNodes(
        self,
        n: int,
        leftChild: List[int],
        rightChild: List[int]
    ) -> bool:
        
        indegree = [0] * n

        # Build indegree array
        for node in range(n):
            left = leftChild[node]
            right = rightChild[node]

            if left != -1:
                indegree[left] += 1
                if indegree[left] > 1:
                    return False

            if right != -1:
                indegree[right] += 1
                if indegree[right] > 1:
                    return False

        # Find root
        roots = [i for i in range(n) if indegree[i] == 0]

        if len(roots) != 1:
            return False

        root = roots[0]

        # DFS traversal
        visited = set()
        stack = [root]

        while stack:
            node = stack.pop()

            if node in visited:
                return False

            visited.add(node)

            left = leftChild[node]
            right = rightChild[node]

            if left != -1:
                stack.append(left)

            if right != -1:
                stack.append(right)

        # Check connectivity
        return len(visited) == n

The implementation begins by constructing the indegree array. Every time a node appears as a child, its indegree increases. If any node receives more than one parent, the function immediately returns False.

Next, the code identifies the root. A valid tree must contain exactly one node with indegree 0. If there are zero roots or multiple roots, the structure cannot be a valid binary tree.

The DFS traversal uses a stack and a visited set. The stack enables iterative traversal without recursion depth concerns. The visited set ensures that cycles are detected immediately.

Finally, the algorithm checks whether every node was visited. If not, the graph is disconnected.

Go Solution

func validateBinaryTreeNodes(n int, leftChild []int, rightChild []int) bool {
	indegree := make([]int, n)

	// Build indegree array
	for node := 0; node < n; node++ {
		left := leftChild[node]
		right := rightChild[node]

		if left != -1 {
			indegree[left]++
			if indegree[left] > 1 {
				return false
			}
		}

		if right != -1 {
			indegree[right]++
			if indegree[right] > 1 {
				return false
			}
		}
	}

	// Find root
	root := -1

	for i := 0; i < n; i++ {
		if indegree[i] == 0 {
			if root != -1 {
				return false
			}
			root = i
		}
	}

	if root == -1 {
		return false
	}

	// DFS traversal
	visited := make([]bool, n)
	stack := []int{root}

	for len(stack) > 0 {
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]

		if visited[node] {
			return false
		}

		visited[node] = true

		left := leftChild[node]
		right := rightChild[node]

		if left != -1 {
			stack = append(stack, left)
		}

		if right != -1 {
			stack = append(stack, right)
		}
	}

	// Check connectivity
	count := 0
	for _, seen := range visited {
		if seen {
			count++
		}
	}

	return count == n
}

The Go implementation closely mirrors the Python version. Instead of Python's set, it uses a boolean slice called visited. The DFS stack is implemented with a slice.

Go does not have Python's list comprehensions, so root detection is done with a standard loop. The implementation also explicitly counts visited nodes at the end because Go slices do not provide a built-in equivalent to Python's len(set) behavior.

Worked Examples

Example 1

n = 4
leftChild  = [1, -1, 3, -1]
rightChild = [2, -1, -1, -1]

Step 1: Build indegree array

Node	Left Child	Right Child	Updated Indegree
0	1	2	[0,1,1,0]
1	-1	-1	[0,1,1,0]
2	3	-1	[0,1,1,1]
3	-1	-1	[0,1,1,1]

Only node 0 has indegree 0, so it is the root.

Step 2: DFS traversal

Stack	Visited	Action
[0]	{}	Start
[1,2]	{0}	Visit 0
[1,3]	{0,2}	Visit 2
[1]	{0,2,3}	Visit 3
[]	{0,1,2,3}	Visit 1

All 4 nodes are visited exactly once.

Result: True

Example 2

n = 4
leftChild  = [1, -1, 3, -1]
rightChild = [2, 3, -1, -1]

Step 1: Build indegree array

Node	Left Child	Right Child	Updated Indegree
0	1	2	[0,1,1,0]
1	-1	3	[0,1,1,1]
2	3	-1	[0,1,1,2]

Node 3 now has indegree 2.

This means node 3 has two parents, which violates binary tree rules.

Result: False

Example 3

n = 2
leftChild  = [1, 0]
rightChild = [-1, -1]

Step 1: Build indegree array

Node	Left Child	Right Child	Updated Indegree
0	1	-1	[0,1]
1	0	-1	[1,1]

No node has indegree 0.

This means there is no root, which implies a cycle.

Result: False

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node and edge is processed a constant number of times
Space	O(n)	Indegree array, visited set, and traversal stack all require linear space

The algorithm performs a single pass to compute indegrees and a single traversal to validate connectivity and detect cycles. Since each node has at most two children, the total number of edges is bounded by 2n, keeping the runtime linear.

Test Cases

from typing import List

class Solution:
    def validateBinaryTreeNodes(
        self,
        n: int,
        leftChild: List[int],
        rightChild: List[int]
    ) -> bool:
        
        indegree = [0] * n

        for node in range(n):
            left = leftChild[node]
            right = rightChild[node]

            if left != -1:
                indegree[left] += 1
                if indegree[left] > 1:
                    return False

            if right != -1:
                indeegree = indegree[right] + 1
                indegree[right] = indeegree
                if indeegree > 1:
                    return False

        roots = [i for i in range(n) if indegree[i] == 0]

        if len(roots) != 1:
            return False

        root = roots[0]

        visited = set()
        stack = [root]

        while stack:
            node = stack.pop()

            if node in visited:
                return False

            visited.add(node)

            if leftChild[node] != -1:
                stack.append(leftChild[node])

            if rightChild[node] != -1:
                stack.append(rightChild[node])

        return len(visited) == n

sol = Solution()

assert sol.validateBinaryTreeNodes(
    4,
    [1,-1,3,-1],
    [2,-1,-1,-1]
) == True  # valid binary tree

assert sol.validateBinaryTreeNodes(
    4,
    [1,-1,3,-1],
    [2,3,-1,-1]
) == False  # node with two parents

assert sol.validateBinaryTreeNodes(
    2,
    [1,0],
    [-1,-1]
) == False  # cycle with no root

assert sol.validateBinaryTreeNodes(
    1,
    [-1],
    [-1]
) == True  # single node tree

assert sol.validateBinaryTreeNodes(
    4,
    [1,-1,-1,-1],
    [-1,-1,-1,-1]
) == False  # disconnected nodes

assert sol.validateBinaryTreeNodes(
    4,
    [1,2,-1,-1],
    [-1,-1,-1,-1]
) == False  # multiple roots

assert sol.validateBinaryTreeNodes(
    5,
    [1,2,3,4,-1],
    [-1,-1,-1,-1,-1]
) == True  # valid chain structure

assert sol.validateBinaryTreeNodes(
    3,
    [1,-1,-1],
    [2,0,-1]
) == False  # cycle exists

assert sol.validateBinaryTreeNodes(
    6,
    [1,3,-1,-1,-1,-1],
    [2,-1,-1,-1,5,-1]
) == False  # disconnected component

assert sol.validateBinaryTreeNodes(
    4,
    [1,-1,-1,-1],
    [2,-1,-1,1]
) == False  # node 1 has two parents

Test	Why
Valid example tree	Confirms normal valid behavior
Node with two parents	Verifies indegree validation
Simple cycle	Ensures cycle detection works
Single node	Tests smallest valid input
Disconnected nodes	Ensures connectivity is checked
Multiple roots	Verifies root uniqueness
Linear chain tree	Confirms skewed trees work
Larger cycle	Tests traversal cycle detection
Separate component	Detects unreachable nodes
Repeated child assignment	Another multiple-parent scenario

Edge Cases

A very important edge case occurs when a node has two parents. This is easy to miss if we only perform DFS traversal from a root. For example, two different nodes may both point to the same child while still forming an otherwise connected structure. A naive traversal might still visit all nodes exactly once and incorrectly conclude the graph is valid. The indegree check prevents this by immediately rejecting any node whose indegree exceeds 1.

Another critical edge case is a cycle. In a cyclic graph, every node may have exactly one parent, making the indegree analysis alone insufficient. For example, node 0 may point to node 1 while node 1 points back to node 0. The DFS traversal handles this correctly by detecting revisits through the visited set.

Disconnected graphs are also subtle. It is possible to have one perfectly valid tree component plus several isolated nodes. Such inputs may still contain exactly one root in the main component, so simply checking for a root is not enough. The final connectivity check ensures that every node is reachable from the root.

A final edge case involves multiple roots. If two separate trees exist, then multiple nodes will have indegree 0. The implementation explicitly counts roots and rejects any structure that does not have exactly one root.