Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem statement
1.2.
Sample Example
2.
Brute Force Approach
2.1.
Steps of Algorithm
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Optimized Approach
3.1.
Steps of Algorithm 
3.2.
Implementation in C++
3.2.1.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What is Hashing?
4.2.
What do you understand by Inorder Traversal?
4.3.
What is a Binary Tree?
5.
Conclusion
Last Updated: Mar 27, 2024

Construct a Binary Tree from the given Parent Array Representation

Author Sarthak
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

Binary Tree is one of the cream topics for the interviewer's perspectives and asking in many coding interviews. Do you want to crack that cream question and be a ninja?

Today, In this blog, we will discuss one of the common problems, i.e., Construct a Binary Tree from a given Parent Array.

Problem statement

Let us look at the problem first.

We are given an array or vector as input that represents a Binary Tree. The nodes are related to their parent by having a parent-child relationship defined as (A[i], i), which means for a particular index, the index of the array shows the node's value, and the value in that index shows the parent of that node. The value -1 in the array indicates that it is the root of the Binary tree. You have to create a Binary Tree out given representation. You can assume that the input array given to you is always valid.

Sample Example

Input:

Int arr[]={3,7,7,4,8,6,4,8,-1,1};

 

Output: 

 

Explanation:

The index of -1 is 8.  So 8 is root Node.  
8 is present at indexes 4 and 7.  So 4 and 7 are left and right child of 8.  
4 is present at index 3 and 6, so 3 and 6 are left and right child of 4.
7 is present in indexes 1 and 2.  So 1 and 2 are left and right child of 7.  
3 is present at index 0, so 0 is left child of 3.
6 is present at index 5, so 5 is left child of 6.
1 is present at index 9, so 9 is left child of 1.

2,0,5,9 are not present in the array, there are no left and right child of these nodes.

Brute Force Approach

Before jumping to the solution, let us understand how we reach our output Binary tree.

The idea here is to recursively find the children of a particular node, attach them with their Parent Node and again work on the child nodes.

Steps of Algorithm

It is a recursive algorithm but BruteForce Approach.

  •  First, we search for an element with the value -1 in the parent array. Therefore, we make a call to Therefore, we make a call to function CreateTree(currentNode = root, size = n, Array = arr) which searches for -1.Let the index of that element be 'rootIndex'. We create a node with the value rootIndex and mark that node as the root for the Tree.
  • Now, the root Node's left and right child will be the index of the root Node in the array.
  • Therefore, we make a recursive call to function CreateTree(currentNode = root, index = rootIndex, parentArray = parent) which searches for elements with value rootIndex in parent array. If such elements are found, then it creates nodes out of the found indices, makes them children of the root, and constructs sub-trees rooted at these created nodes(children) by making recursive calls. 
  • The base case of this recursive function createTree(currentNode, sizeofArray, parent) occurs when it cannot find elements with the value 'index' in the parent array. This means we found the wrong index(-1). This implies that the currentNode is a leaf node, and therefore it does not have any sub-trees rooted in itself.
  • Calculate the Inorder of the Binary tree Recursively, which gives the Output of our Algorithm.

Implementation in C++

//Program to Construct a Binary Tree From Given Array
#include <iostream>
using namespace std;
class Node
{
public:
   int data;
   Node *left, *right;
   Node(int value)
   {
       this->data = value;
       this->left = NULL;
       this->right = NULL;
   }
};
// Inorder Traversing of the Tree.
void Traversing(Node *node)
{
   if (node != NULL)
   {
       Traversing(node->left);
       cout << node->data << " ";
       Traversing(node->right);
   }
}
// Getting Index/Element By searching in the array
int getIndex(int arr[], int n, int value)
{
   int element = -1, i = 0;
   while (i < n)
   {
       // If the value is found, change the value to -2 so that this // //value is not repeated in the Tree.
       if (arr[i] == value)
       {
           element = i;
           arr[i] = -2;
           break;
       }
       i++;
   }
   return element;
}
// Creating Binary Tree Using Recursion
Node *CreateTree(int arr[], int n, int element)
{
   // Finding the value of Element from the Index
   element = getIndex(arr, n, element);
   if (element != -1)
   {
       Node *head = new Node(element);
       // Recursively Calling for Left Node
       head->left = CreateTree(arr, n, element);
       // Recursively Calling for Left Node
       head->right = CreateTree(arr, n, element);
       return head;
   }
   // element is not present in the array
   else
   {
       return NULL;
   }
}
int main()
{
   Node *root = NULL;
   int arr[] = {3, 7, 7, 4, 8, 6, 4, 8, -1, 1};
   int n = sizeof(arr) / sizeof(arr[0]);
   // First Finding root node first(having value equals -1)
   root = CreateTree(arr, n, -1);
   cout << "Inorder Traversal of Output Binary Tree is" << endl;
   Traversing(root);
   return 0;
}

 

Output:

Inorder Traversal of Binary Tree is
0 3 4 5 6 8 9 1 7 2

 

Complexity Analysis

Time complexity

O(n²), where n is the size of the array.

As we are calling a function ’getIndex’  inside the function ‘CreateTree’ means we are using two loops and both take a maximum of O(n). Hence our time complexity is O(n²).

Space complexity

O(H), where H is the height of the Binary Tree.

The algorithm uses recursion, hence which creates a stack of maximum size H..Hence space complexity would be O(H).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimized Approach

We can use Hashmap or array instead of the long BruteForce Approach. We can create n tree nodes with values from 0 to n-1 and store them in a map or array. Then we can traverse the given array and form the Tree by setting up a Relationship defined as (A[i], i) for every index i in the array. Hence, we can easily make our binary Tree.

Steps of Algorithm 

  • We are using Hashmap or Unordered_map of <int , Node*> type. Here, the key will be of Int type, and the mapped value will be of Node pointer type.
  • Now, we will traverse from 0 to n-1 and create a mapping of value to the node. Hence, we create n tree nodes having values from 0 to n-1.
  • Now, we will traverse our array; if the value in the array is -1, point the root pointer to the current node.
  • We will have a pointer temp on our current node.
  • Else, We will check for the parent left child; if present, we will map the node to its right child (having value i).
  • It means the node doesn't have a left child, so we will map the node to its left child.
  • Return root.

Implementation in C++

//Program to Construct a Binary Tree From Given Array
#include <iostream>
#include <unordered_map>
using namespace std;
struct Node
{
    int data;
    Node *left, *right;
    Node(int data)
    {
        this->data = data;
        this->left = this->right = NULL;
    }
};
// Performing Inorder traversal on the Tree to Find Output
void Inorder(Node *temp)
{
    if (temp == NULL)
    {
        return;
    }
    Inorder(temp->left);
    cout << temp->data << " ";
    Inorder(temp->right);
}
// Creating a binary tree from the given parent array
Node *CreateTree(int ParentArray[], int n)
{
    // creating an Unordereed_map or Hashmap.
    unordered_map<int, Node *> map;
    // creating nodes having value from 0 to n-1 and store them in a map
    for (int i = 0; i < n; i++)
    {
        map[i] = new Node(i);
    }
    // Root node of a binary tree
    Node *root = NULL;
    // traversing the parent array and building the tree
    for (int i = 0; i < n; i++)
    {
        // If the values in the array is -1 make the root point to the current node having the value i.
        if (ParentArray[i] == -1)
        {
            root = map[i];
        }
        // get the child for the current node.
        else
        {
            Node *ptr = map[ParentArray[i]];
            // if the parent's left child is filled, map the node to its right child
            if (ptr->left)
            {
                ptr->right = map[i];
            }
            // else map the node to the left child of the parent node
            else
            {
                ptr->left = map[i];
            }
        }
    }
    // return root
    return root;
}
int main()
{
    int parent[] = {3, 7, 7, 4, 8, 6, 4, 8, -1, 1};
    int n = sizeof(parent) / sizeof(parent[0]);
    Node *root = CreateTree(parent, n);
    cout << "Inorder Traversal of Output Binary Tree is " << endl;
    Inorder(root);
    return 0;
}

 

Output:

Inorder Traversal of Output Binary Tree is
0 3 4 5 6 8 9 1 7 2

 

Complexity Analysis

Time complexity

O(n), We are traversing the Array only once which takes O(n).

Space complexity

O(n), We have created Hashmap which takes O(n) space. Hence space complexity is O(n).

Frequently Asked Questions

What is Hashing?

Hashing is a process of mapping keys and values into the hash table by using a hash function. It is used for faster access to elements. 

What do you understand by Inorder Traversal?

We can define the Inorder Traversal as, i.e., recursively going to the left subtree, visiting the root, and then going to the right subtree and forming the Inorder Traversal.

What is a Binary Tree?

Binary means two. A tree is a data structure in which every element have a maximum of 2 children is called a binary tree. These children are called Left child and Right Child.

Conclusion

In this article, we discussed how to Construct a Binary Tree from a given Array representation. We have discussed the BruteForce Approach as well as the optimized approach of our problem using Hashmap and also saw its time and space complexity.

We hope you learned from this problem and have seen how Hashmap works and helps us to make our code easy.

Suggested problems are Construct a Binary Tree From Preorder and Postorder, Construct a Binary Tree From its Linked-List Representation, and many more.

Refer to our guided paths on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingDBMSSystem DesignWeb Development, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. You must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
Construct a Binary Tree from a given Postorder and Inorder Traversal
Next article
Replace each node in a binary tree with the sum of its inorder predecessor and successor
Live masterclass