Construct Binary Tree from Parent Array

Given an array parent that is used to represent a tree. The array indices (0-based indexing) are the values of the tree nodes and parent[i] denotes the parent node of a particular node. The parent of the root node would always be -1, as there is no parent for the root. Construct the standard linked representation of Binary Tree from this array representation and return the root node of the constructed tree.

Note: If two elements have the same parent, the one that appears first in the array will be the left child and the other is the right child. You don’t need to print anything, the driver code will print the level order traversal of the returned root node to verify the output.

Examples:

Input: parent[] = [-1, 0, 0, 1, 1, 3,5]
Output: 0 1 2 3 4 5 6
Explanation: the tree generated
will have a structure like 
          0
        /   \
       1     2
      / \
     3   4
    /
   5
 /
6

Input: parent[] = [2, 0, -1]
Output: 2 0 1
Explanation: the tree generated will
have a sturcture like
             2
            /   
           0      
          /   
         1     

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)

Constraints:
1 ≤ parent.size() ≤ 10³

Approach01:

class Solution {
  public:
    Node *createTree(vector<int> parent) {
        unordered_map<int, Node*> nodeMap;
        for(int i = 0; i < parent.size(); i++) {
            nodeMap[i] = new Node(i);
        }
        int rootValue = -1;
        for(int i = 0; i < parent.size(); i++) {
            int parentIndex = parent[i];
            int childIndex = i;
            if(parentIndex == -1) {
                rootValue = i;
                continue;
            }
            if(nodeMap[parentIndex]->left == nullptr) {
                nodeMap[parentIndex]->left = nodeMap[childIndex];
            } else {
                nodeMap[parentIndex]->right = nodeMap[childIndex];
            }
        }
        return nodeMap[rootValue];
    }
};

class Solution:
    def createTree(self, parent):
        node_map = {}
        for i in range(len(parent)):
            node_map[i] = Node(i)
        
        root_value = -1
        for i in range(len(parent)):
            parent_index = parent[i]
            child_index = i
            if parent_index == -1:
                root_value = i
                continue
            if node_map[parent_index].left is None:
                node_map[parent_index].left = node_map[child_index]
            else:
                node_map[parent_index].right = node_map[child_index]
        
        return node_map[root_value]

Time Complexity

• Node Creation and Mapping:

  Creating the nodeMap and populating it with nodes takes \( O(n) \) time, where \( n \) is the number of elements in the parent vector.

• Building the Tree:

  Iterating through the parent vector to set the left and right children for each node also takes \( O(n) \) time.

• Overall Time Complexity:

  The overall time complexity is \( O(n) + O(n) = O(n) \).

Space Complexity

• Auxiliary Space for Node Map:

  The nodeMap stores up to \( n \) nodes, resulting in \( O(n) \) space usage.

• Additional Space for Nodes:

  Each node is created dynamically and occupies \( O(1) \) space. Since there are \( n \) nodes, this results in \( O(n) \) space usage.

• Overall Space Complexity:

  The overall space complexity is \( O(n) \) for the nodeMap and the nodes.