Problem Explanation

In this problem, we have to form a binary tree (if possible) with given nodes. We are given n nodes indexed from 0 to n-1. For each node i, we are also given their left and right children (leftChild[i] and rightChild[i]). If a node has no left or right child, the left or right child is denoted as -1.

A valid binary tree needs to meet two requirements:

1. Each node can be reached from the root
2. Only one node is considered as a root node, which means only one node should not be the right or left child for any node in the tree.

We need to validate whether a binary tree could be formed from these nodes. If we can form a binary tree it returns true, otherwise false.

Approach

The basic idea for the approah is that all nodes must be reachable from exactly one other node, with the exception of the root node, which has to be reachable from 0 nodes. We use the Depth-First Search (DFS) approach to count the nodes starting from the root node and compare it to n at the end.

1. We create an inDegree array where each entry will represent how many times each node appears as a child in the input.
2. Traverse the leftChild and rightChild arrays, increasing the inDegree of each child node.
3. Check the inDegree table to find the root (should be 0).
4. Run the DFS with the root node. Count the number of nodes visited.
5. If the count is equal to n, all the nodes have been visited, and hence a tree is possible.

Example

Take the input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1].

• The inDegree table will be [0,1,1,1]. Node 0 is the root.
• Running the DFS starting from the root node, we find we can visit all nodes, hence the tree can be constructed and we return true.

Python Solution

1
2python
3class Solution:
4    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
5        in_degree = [0]*n
6        root = -1
7
8        #update inDegree count for leftChild and rightChild
9        for child in leftChild:
10            if child != -1:
11                in_degree[child] += 1
12                if in_degree[child] > 1:
13                    return False
14
15        for child in rightChild:
16            if child != -1:
17                in_degree[child] += 1
18                if in_degree[child] > 1:
19                    return False
20
21        #find root
22        for i in range(n):
23            if in_degree[i] == 0:
24                if root == -1:
25                    root = i
26                else:
27                    return False
28                
29        #if no root
30        if root == -1:
31            return False
32
33        #check if all nodes are reachable from root
34        if self.dfs(root, leftChild, rightChild) == n:
35            return True
36        else:
37            return False
38            
39    def dfs(self, root, leftChild, rightChild):
40        if root == -1:
41            return 0
42        else:
43            return 1 + self.dfs(leftChild[root], leftChild, rightChild) + self.dfs(rightChild[root], leftChild, rightChild)

Java Solution

1
2java
3class Solution {
4    public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
5        int[] inDegree = new int[n];
6
7        for (int child : leftChild)
8            if (child != -1 && ++inDegree[child] == 2)
9                return false;
10
11        for (int child : rightChild)
12            if (child != -1 && ++inDegree[child] == 2)
13                return false;
14        
15        int root = -1;
16        for (int i = 0; i < n; ++i)
17            if (inDegree[i] == 0)
18                if (root == -1)
19                    root = i;
20                else
21                    return false;
22
23        if (root == -1)
24            return false;
25
26        return dfs(root, leftChild, rightChild) == n;
27    }
28    
29    private int dfs(int root, int[] leftChild, int[] rightChild) {
30        if (root == -1)
31            return 0;
32        return 1 + 
33            dfs(leftChild[root], leftChild, rightChild) +
34            dfs(rightChild[root], leftChild, rightChild);
35    }
36}

JavaScript Solution

1
2javascript
3var validateBinaryTreeNodes = function(n, leftChild, rightChild) {
4  const inDegree = Array(n).fill(0);
5  let root = -1;
6  
7  for (let child of leftChild) {
8    if (child !== -1) {
9      inDegree[child]++;
10      if (inDegree[child] > 1) {
11        return false;
12      }
13    }
14  }
15  
16  for (let child of rightChild) {
17    if (child !== -1) {
18      inDegree[child]++;
19      if (inDegree[child] > 1) {
20        return false;
21      }
22    }
23  }
24  
25  for (let i = 0; i < n; i++) {
26    if (inDegree[i] === 0) {
27      root = i;
28      break;
29    }
30  }
31  
32  if (root === -1) {
33    return false;
34  }
35  
36  return dfs(root, leftChild, rightChild) === n;
37};
38
39function dfs(root, leftChild, rightChild) {
40  if (root === -1) {
41    return 0;
42  }
43  
44  return (
45    1 +
46    dfs(leftChild[root], leftChild, rightChild) +
47    dfs(rightChild[root], leftChild, rightChild)
48  );
49}

C++ Solution

1
2cpp
3class Solution {
4public:
5    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
6        vector<int> inDegree(n);
7        int root = -1;
8
9        // If inDegree of any node > 1, return false
10        for (const int child : leftChild)
11            if (child != -1 && ++inDegree[child] == 2)
12                return false;
13
14        for (const int child : rightChild)
15            if (child != -1 && ++inDegree[child] == 2)
16                return false;
17
18        // Find the root (node with inDegree == 0)
19        for (int i = 0; i < n; ++i)
20            if (inDegree[i] == 0)
21                if (root == -1)
22                    root = i;
23                else
24                    return false;  // Multiple roots
25
26        // didn't find the root
27        if (root == -1)
28            return false;
29
30        return countNodes(root, leftChild, rightChild) == n;
31    }
32
33private:
34    int countNodes(int root, const vector<int>& leftChild,
35                const vector<int>& rightChild) {
36    if (root == -1)
37        return 0;
38    return 1 +  
39        countNodes(leftChild[root], leftChild, rightChild) +
40        countNodes(rightChild[root], leftChild, rightChild);
41  }
42};

C# Solution

1
2csharp
3public class Solution {
4    public bool ValidateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
5        int[] inDegree = new int[n];
6        int root = -1;
7
8        foreach(int child in leftChild){
9            if(child != -1){
10                inDegree[child]++;
11                if(inDegree[child] > 1){
12                    return false;
13                }
14            }
15        }
16
17        foreach(int child in rightChild){
18            if(child != -1){
19                inDegree[child]++;
20                if(inDegree[child] > 1){
21                    return false;
22                }
23            }
24        }
25
26        for(int i= 0; i<n; i++){
27            if(inDegree[i] == 0){
28                if(root == -1){
29                    root = i;
30                }
31                else{
32                    return false;
33                }
34            }
35        }
36
37        return root != -1 && Dfs(root, leftChild, rightChild) == n;
38    }
39    
40    private int Dfs(int root, int[] leftChild, int[] rightChild){
41        if(root == -1)
42            return 0;
43        return 1 + 
44            Dfs(leftChild[root], leftChild, rightChild)+
45            Dfs(rightChild[root], leftChild, rightChild);
46    }
47}

In the above solutions, we initially check the incoming degree for each node is no more than 1 (each node only has one direct parent or none). If we detect any node with an incoming degree of more than 1, we return false. Similarly, we check for only one root node. If there no root nodes or more than one, we return false. If all checks pass, we finally perform a DFS tree traversal from the root node and check if we have visited all "n" nodes. If we have, we return true; otherwise, false. This checks ensures that all the nodes are indeed reachable from the root node.# Time and Space Complexity

For each of the above solutions, the time complexity is O(n) as we are traversing each node once when we find the inDegree, find the root, and perform the DFS.

The space complexity of these solutions is also O(n) because we use extra space for the inDegree array where n is the number of nodes. Additionally, space is also required for the recursive calls stack space during the DFS, which in the worst-case can go up to n levels deep.

conclusion

From the above solutions, we can conclude that we can determine if a binary tree is valid by tracking how many times each node appears as a child (the inDegree) and by performing a depth-first search (DFS). This allows us to verify that every node is reachable exactly once from the root node (except for the root node which should be reachable 0 times), and that all nodes are reachable from the root node. This approach works in languages such as Python, Java, Javascript, C++, and C#. The time complexity is linear which makes this solution efficient even for large numbers of nodes. This makes it handy while dealing with certain types of binary tree problems where it's essential to validate the formation of the tree before performing any operations. If the binary tree is invalid, it can lead to unexpected behavior or runtime errors, causing the solution to fail.