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 - 1To 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:
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).
C++
Java
Python
C#
JavaScript
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.
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:
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.
C++
Java
Python
C#
JavaScript
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.
| 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. |
Balanced Binary Tree - Leetcode 110 - Python • NeetCode • 306,385 views views
Watch 9 more video solutions →Practice Validate Binary Tree Nodes with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor