Construct a Binary Tree from the given Parent Array Representation

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;
}

You can also try this code with Online C++ Compiler

Run Code

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).