Problem

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.

Examples

Example 1:

graph TD
    A(0)
    A --- B(1)
    A --- C(2)
    C --- D(3)
    C ~~~ N1:::hidden

classDef hidden display:none
  
1
2

Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
Output: true

Example 2:

graph TD
    A(0)
    A --- B(1)
    A --- C(2)
    B --- D(3)
    C --- D(3)
  
1
2

Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1]
Output: false

Example 3:

graph TD
    A(0)
    A --- B(1)
    B --- A(0)
  
1
2

Input: n = 2, leftChild = [1,0], rightChild = [-1,-1]
Output: false

Solution

Method 1 - Count Indegree and Nodes

The problem requires determining whether the given nodes form exactly one valid binary tree. The criteria for forming a valid binary tree include:

  1. Only one root: There should be exactly one node with no parent.
  2. No cycles: Each node should belong to the tree structure and should be reachable from the root.
  3. No shared children: A node must have only one parent.

To solve this, the following steps are followed:

  1. Compute the in-degree of each node. Nodes with an in-degree greater than 1 are invalid (violating the “no shared children” property).
  2. Identify the root. A valid binary tree should have exactly one node with an in-degree of 0 (root node).
  3. Perform a traversal starting from the root and verify that all nodes are reachable, ensuring there are no cycles and the structure is fully connected.
  4. Return true only if these conditions are satisfied.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

public class Solution {
    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
        int[] inDegree = new int[n];
        for (int i = 0; i < n; i++) {
            if (leftChild[i] != -1) inDegree[leftChild[i]]++;
            if (rightChild[i] != -1) inDegree[rightChild[i]]++;
        }
        
        // Determine the root (node with in-degree 0)
        int root = -1;
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                if (root != -1) return false; // More than one root
                root = i;
            }
            if (inDegree[i] > 1) return false; // Shared children
        }
        if (root == -1) return false; // No root found
        
        // Perform DFS to check connectivity
        boolean[] visited = new boolean[n];
        Stack<Integer> stack = new Stack<>();
        stack.push(root);
        
        while (!stack.isEmpty()) {
            int curr = stack.pop();
            if (visited[curr]) return false; // Cycle detected
            visited[curr] = true;
            
            int left = leftChild[curr], right = rightChild[curr];
            if (left != -1) stack.push(left);
            if (right != -1) stack.push(right);
        }
        
        // Check if all nodes are visited
        for (boolean v : visited) {
            if (!v) return false;
        }
        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution:
    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
        in_degree = [0] * n
        for i in range(n):
            if leftChild[i] != -1:
                in_degree[leftChild[i]] += 1
            if rightChild[i] != -1:
                in_degree[rightChild[i]] += 1
        
        # Determine the root
        root = -1
        for i in range(n):
            if in_degree[i] == 0:
                if root != -1:
                    return False  # More than one root
                root = i
            if in_degree[i] > 1:
                return False  # Shared children
        if root == -1:
            return False  # No root found
        
        # Perform DFS to check connectivity
        visited = [False] * n
        
        def dfs(node: int):
            if node == -1 or visited[node]:
                return
            visited[node] = True
            dfs(leftChild[node])
            dfs(rightChild[node])
        
        dfs(root)
        
        # Check if all nodes are visited
        return all(visited)

Complexity

  • Time: O(n) (we traverse the nodes and their relations).
  • Space: O(n) (due to auxiliary structures like visited nodes and adjacency representation).