Validate Binary Tree Nodes - Solution & Explanation

Q: Is Validate Binary Tree Nodes easy or hard?

LeetCode classifies this problem as Medium. The difficulty comes from recognizing that the arrays represent a directed graph and that a valid binary tree must satisfy three constraints: one root, no node with multiple parents, and no cycles while remaining fully connected.

Q: How to solve Validate Binary Tree Nodes in O(n)?

Scan the leftChild and rightChild arrays to compute in-degrees and detect nodes with multiple parents. Identify the root as the only node with in-degree 0. Perform a DFS or BFS from that root and mark visited nodes. If you visit all n nodes and never encounter a previously visited node, the structure forms a valid binary tree.

Q: What is the best approach for Validate Binary Tree Nodes?

The most common approach uses in-degree counting plus a DFS traversal. First ensure every node has at most one parent and identify the single root (node with in-degree 0). Then run DFS from that root to verify there are no cycles and all nodes are reachable. This runs in O(n) time and O(n) space.

Q: What data structure is used in Validate Binary Tree Nodes?

Typical solutions rely on graph traversal structures such as adjacency relationships from the child arrays, a visited set for DFS, and an in-degree array. Some implementations use a Union-Find (Disjoint Set Union) structure to detect cycles and maintain connected components.

Q: What is the time complexity of Validate Binary Tree Nodes?

Both common solutions run in O(n) time where n is the number of nodes. Each node and edge is processed at most once while checking parents and performing DFS or Union-Find operations. Space complexity is O(n) for tracking parents, visited nodes, or disjoint set structures.

Q: Validate Binary Tree Nodes Python or Java solution approach

In Python or Java, compute an in-degree array while scanning child pointers. Reject nodes with in-degree greater than one. Find the root, then run DFS or BFS using a stack or queue to visit children. Ensure every node is visited exactly once to confirm the graph forms a valid binary tree.

Q: Is Validate Binary Tree Nodes asked at Google, Amazon, or Meta?

Binary tree validation and graph cycle detection problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variants often test detecting cycles, verifying tree structure, or ensuring single-parent constraints using DFS, BFS, or Union-Find.

MediumTree Depth-First Search Breadth-First Search Union Find24 min readAsked at: Microsoft, Meta, Google

Practice this problem

Problem Statement

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.length
1 <= n <= 10⁴
-1 <= leftChild[i], rightChild[i] <= n - 1

Approach Overview

Problem 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 1: Disjoint Set Union (DSU)

To solve this problem using the Disjoint Set Union (DSU) approach, we aim to union nodes based on their parent-child relationships. A valid tree should follow these rules:

There should be exactly one node with no parent, which serves as a root, ensuring all nodes belong to one connected component.
A tree should not have cyclic dependencies between nodes.
We use a DSU to union nodes and check for cycles. Also, we'll use an array to track nodes' parents, identifying the root node.

The solution creates a parent array to track the roots of each node using the find function with path compression. The unionFind function unites two components. If unionFind finds that two nodes are already connected, it indicates a cycle. The solution verifies each node only has one parent and no cycle exists by unionizing their parent-child relations. Finally, it ensures exactly one node has no parent (root node).

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n), where n is the number of nodes, due to each union and find operation being nearly constant with path compression.

Space Complexity: O(n) for the parent array.

Try this approach in the editor →

Approach 2: In-degree with Depth-First Search (DFS)

This approach involves calculating the in-degree of each node and checking connectivity via a DFS. The key aspects of a tree like single-root presence and cycle-checking can be managed by:

Counting in-degrees with the premise that a tree's nodes (except the root) have exactly one parent.
Deploying a DFS to ensure all nodes are reachable from a root node, confirming no cycles are involved.
Checking if we can visit exactly all the nodes starting from the found root node.

In this C solution, the algorithm starts by calculating the in-degree for each node, which should equal zero for the root node. A DFS checks connectivity from a root node, ensuring all nodes are part of one connected graph and are reachable. Each node is visited once, ensuring an entire traversal defines the single connected component rule of trees.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n), since each node and its immediate edges are evaluated once in each step, including in-drives calculations and DFS.

Space Complexity: O(n) for holding visited tracking and in-degree counts.

Try this approach in the editor →

Approach 3: Union-Find

We can traverse each node i and its corresponding left and right children l, r, using an array vis to record whether the node has a parent:

If the child node already has a parent, it means there are multiple fathers, which does not meet the condition, so we return false directly.
If the child node and the parent node are already in the same connected component, it means a cycle will be formed, which does not meet the condition, so we return false directly.
Otherwise, we perform a union operation, set the corresponding position of the vis array to true, and decrease the number of connected components by 1.

After the traversal, we check whether the number of connected components in the union-find set is 1. If it is, we return true, otherwise, we return false.

The time complexity is O(n times \alpha(n)), and the space complexity is O(n). Where n is the number of nodes, and \alpha(n) is the inverse Ackermann function, which is less than 5.

Code

Python Java C++Go

Python

Java

C++

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Disjoint Set Union (DSU)	Time Complexity: O(n), where n is the number of nodes, due to each union and find operation being nearly constant with path compression. Space Complexity: O(n) for the parent array.
In-degree with Depth-First Search (DFS)	Time Complexity: O(n), since each node and its immediate edges are evaluated once in each step, including in-drives calculations and DFS. Space Complexity: O(n) for holding visited tracking and in-degree counts.
Union-Find	—

Detailed Complexity Analysis

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

Video Solution

Validate Binary Tree Nodes | Using Binary Tree Properties | BFS | META | Leetcode - 1361 • codestorywithMIK • 13,857 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Validate Binary Tree Nodes easy or hard?

LeetCode classifies this problem as Medium. The difficulty comes from recognizing that the arrays represent a directed graph and that a valid binary tree must satisfy three constraints: one root, no node with multiple parents, and no cycles while remaining fully connected.

How to solve Validate Binary Tree Nodes in O(n)?

Scan the leftChild and rightChild arrays to compute in-degrees and detect nodes with multiple parents. Identify the root as the only node with in-degree 0. Perform a DFS or BFS from that root and mark visited nodes. If you visit all n nodes and never encounter a previously visited node, the structure forms a valid binary tree.

What is the best approach for Validate Binary Tree Nodes?

The most common approach uses in-degree counting plus a DFS traversal. First ensure every node has at most one parent and identify the single root (node with in-degree 0). Then run DFS from that root to verify there are no cycles and all nodes are reachable. This runs in O(n) time and O(n) space.

What data structure is used in Validate Binary Tree Nodes?

Typical solutions rely on graph traversal structures such as adjacency relationships from the child arrays, a visited set for DFS, and an in-degree array. Some implementations use a Union-Find (Disjoint Set Union) structure to detect cycles and maintain connected components.

What is the time complexity of Validate Binary Tree Nodes?

Both common solutions run in O(n) time where n is the number of nodes. Each node and edge is processed at most once while checking parents and performing DFS or Union-Find operations. Space complexity is O(n) for tracking parents, visited nodes, or disjoint set structures.

Validate Binary Tree Nodes Python or Java solution approach

In Python or Java, compute an in-degree array while scanning child pointers. Reject nodes with in-degree greater than one. Find the root, then run DFS or BFS using a stack or queue to visit children. Ensure every node is visited exactly once to confirm the graph forms a valid binary tree.

Is Validate Binary Tree Nodes asked at Google, Amazon, or Meta?

Binary tree validation and graph cycle detection problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variants often test detecting cycles, verifying tree structure, or ensuring single-parent constraints using DFS, BFS, or Union-Find.

Ready to solve this problem?

Practice Validate Binary Tree Nodes with our built-in code editor and test cases.

Practice on FleetCode

Binary Tree Inorder Traversal

Unique Binary Search Trees II

Problem Info

DifficultyMedium

Acceptance43.8%

Approaches3

Reading time24 min

Asked at

Microsoft Meta Google

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Disjoint Set Union (DSU)

Code

Complexity

Approach 2: In-degree with Depth-First Search (DFS)

Code

Complexity

Approach 3: Union-Find

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents