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.
Explanation of the problem 
1.3.
Sample Example 
2.
Approach to the problem 
2.1.
Steps of the algorithm 
2.2.
Implementation in C++ 
2.3.
Complexity Analysis
3.
Frequently Asked Questions 
3.1.
What is a tree?
3.2.
What is the difference between a complete binary tree and a full binary tree? 
3.3.
What are the different types of traversals of a binary tree?
4.
Conclusion
Last Updated: Mar 27, 2024

Construct a Complete Binary Tree from given Array in Level Order Fashion

Author Vidhi Singh
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction 

Data Structures and Algorithms play a vital role in the technical interviews. Tree is a topic that most interviewers tend to test. It seems to be a perfect concept to know a candidate’s knowledge of programming concepts and logic. 

So, in this article, we will discuss one such problem related to trees. 

Also See, Binary Tree Postorder Traversal.

Problem Statement 

You are supposed to construct a complete binary tree from an array of elements. The elements are given in an array arranged in a level order fashion. 

Explanation of the problem 

So, according to the question, you will be given an array of elements that are to be used to form a complete binary tree. The catch here is that the elements are arranged in the array in a level order manner. By level order, it means that all the elements in the same level in the tree are stored one after the other. 

For the above tree, the array given will be :
elements[]={‘A’,’B’,’C’,’D’,’E’,’F’}  
 

Now, a complete binary tree is a binary tree such that all the levels of the binary tree are completely filled except the lowest one. Also, the filling should start from the left side.  

 
 So, from the elements of the array, you are to form a complete binary tree. While doing so, you need to keep in mind that elements in the array are stored in a level order manner.

Sample Example 

If the given array is as follows:
elements[]={‘A’,’B’,’C’,’D’,’E’}

Then, the complete binary tree is as follows:

Approach to the problem 

While thinking about the solution to the problem, we need to constantly think about the point that elements are arranged in a level order fashion. It is important because this is the only clue to how actually a tree will be formed. 

Now, one thing more, we cannot move from child to parent node. This is not possible in trees. Only navigating from the parent node to the children nodes is possible, so this is another observation. 

So, if you observe carefully in the sample example, child nodes of ‘A’ are ‘B’ and ‘C’. The index of ‘A’ is 0, ‘B’ is 1 and ‘C’ is 2. And, the children nodes of ‘B’ are ‘D’ and ‘E’. The index of ‘B’ is 1, ‘D’ is 3 and ‘E’ is 4. 

So, for the parent node with index ‘t’, the children node will be on the index ‘2t+1’ and ‘2t+2’. 

Therefore, we keep the 0th index element as the root node and then keep its left and right child as the element on the index 1 and 2. Then we move to the 1st index element, allocate its left and right child with the same technique, and continue doing some till all the elements are used up.  

Steps of the algorithm 

  1. Make the 0th index node the root node. 
  2. Allocate the left node and right node as the 2t+1 and 2t+2 respectively if the index of the parent is t.
  3. If 2t+1 or 2t+2 index is out of bound then, that child is not present. 
  4. Move to the next index 
  5. Repeat steps 2, 3, and 4 till all the elements are used up. 

Implementation in C++ 

#include<bits/stdc++.h>
using namespace std;
class node      //Node of the tree 
{
   public:
        char val;
        node* left_child,*right_child;
};

node* new_node(int data)        //New node of the tree
{
   node* t=new node;
   t->val=data;
   t->left_child=t->right_child=NULL;
   return t;
}

node* complete_tree(char elements[],node* root,int i,int size)      //Constructing the tree
{
    if(i<size) 
    {
        node* t=new_node(elements[i]);
        root=t;
        root->left_child=complete_tree(elements,root->left_child,2*i+1,size);
        root->right_child=complete_tree(elements,root->right_child,2*i+2,size);
    }
    	return root;
}

void inorder_traversal(node* root)      //Inorder traversal of the tree
{
    if(root==NULL) 
        return;
    
    inorder_traversal(root->left_child);
    cout<<root->val<<" ";
    inorder_traversal(root->right_child);
   
}

int main() 
{
	char elements[]={'A','B','C','D','E'};
	int size=sizeof(elements)/sizeof(elements[0]);
	node* root=complete_tree(elements,root,0,size);
	cout<<"Inorder traversal of the complete  binary tree: ";
	inorder_traversal(root);
        return 0;
} 

 

Output:

Inorder traversal of the complete  binary tree: D B E A C  

Complexity Analysis

Time Complexity: O(n) 
Here, ‘n’ is the total nodes in the tree. 

Space Complexity: O(n) 
The space is allocated to the recursion stack. 

Check out this problem - Mirror A Binary Tree

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

Frequently Asked Questions 

What is a tree?

A tree is a data structure that stores data in a hierarchical manner in form of nodes. A node stores some data and addresses of its child nodes.

What is the difference between a complete binary tree and a full binary tree? 

 A complete binary tree is a binary tree where every level, except the last one, is completely occupied, and all nodes are as far left as possible whereas a full binary tree is a binary tree where every node other except the leaves has two children nodes.

What are the different types of traversals of a binary tree?

The most common traversals of the binary tree are: 

  1. Preorder traversal: Visiting the node, the left child, then the right child
  2. Inorder traversal: Visiting the left child, node, then the right child
  3. Postorder traversal: Visiting the left child, the right child, then the node 

Conclusion

This article extensively discusses the programming problem: Construct a complete binary tree from given array in level order fashion along with their pseudocode, implementation, and time trade-offs

We hope that this blog has helped you enhance your knowledge regarding Constructing a complete binary tree from given array in level order fashion, and if you would like to learn more, check out our articles on Coding Ninjas Blogs
You can refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSQLSystem Design, and many more!

 

Recommended problems -

 

If you want to test your competency in coding, you may check out the Mock Test Series and participate in the Contests organized on Coding Ninjas Studio! But if you have just started your learning process and are 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 Courses to give your career an edge over others!

Do upvote our blog to help other ninjas grow. 

Happy Coding! 

Previous article
Construct a special tree from given preorder traversal
Next article
Construct Full Binary Tree using its Preorder traversal and Preorder traversal of its mirror tree
Live masterclass