In this problem, we are given a linked list representation of a tree, and our task is to convert it into a complete binary tree.

It might look intimidating initially, but if you are familiar with level order traversal, it will be effortless for you to come up with a solution. We are going to use level order traversal with a queue in the given approach.

Problem Statement

Construct a Complete Binary Tree from its Linked List Representation.

Test Case

Let us take a test case to understand the problem better,

Here the input linked list is 1->2->3->4->5->6, and the corresponding resultant binary tree is shown in the diagram.

So, the inorder traversal of this binary tree is clearly, 4 2 5 1 6 3.

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

Approach

At first, we will input the linked list and then reverse it (as the input nodes are inserted at the beginning of the linked list). Then, we convert the linked list into a binary tree and finally print the in-order traversal of the tree.

In a typical array representation of a tree, if a node is stored at index i, it’s left child can be found at

2*i + 1

Its right child can be found at

2*i + 2

In the case of an array, we can directly access a node’s left and right child using the above formula. But what should we do if a linked list representation of a tree is given?

We will have to traverse through all the nodes for a linked list to get hold of a node’s left and right child.

Also, if you notice carefully, the sequence of nodes in the linked list representation is the same as the level order traversal of the output tree in the above test case.

The sequence of linked list nodes is: 1->2->3->4->5->6,

and the level order traversal of the binary tree is 1 2 3 4 5 6.

So in the input, we are given the level order traversal of the binary tree.

In the solution, we first create an empty queue and add the head of the linked list to the queue. This head of the linked list is going to be the root of the tree. Then, we run a while loop and add the next two nodes of the linked list in the queue. These two nodes are also connected to the parent/root node of the tree and are the left and right children of the root node.

In our example test case,

1->2->3->4->5->6

First 1 is added to the queue, and then 2 and 3 are enqueued.

So the root of the tree (1) has two children now -a left child (2) and a right child (3).

Once that’s done, we pop the parent/root node (1) and repeat this process until the queue gets empty.

In the next iteration of the while loop, the next two nodes of the linked list, i.e. 4 and 5, are added to the queue and connected to their respective parent node (2) as left and right children. At the end of the while loop, we dequeue 2.

In the next iteration, the last node of the input linked list, i.e. 6 is enqueued. It is connected to its parent node (3) as the left child. Then node 3 gets dequeued.

Now, 4,5, and 6 are the only remaining nodes in the queue and as we reach the end of the linked list, we come out of the while loop.

Finally, the in-order traversal of the constructed tree is printed.

Steps of algorithm

Create an empty queue.

Create the root of the tree using the data part of the head of the given linked list.

Enqueue the node.

Run a while loop until we reach the last node of the linked list,

Connect two nodes to the root node - the first one as the left child and the second as the right child.

#include <bits/stdc++.h>
using namespace std;
// Link list Node
struct LL_Node
{
int data;
struct LL_Node *next;
LL_Node(int x)
{
data = x;
next = NULL;
}
};
// Tree Node
struct Tree_Node
{
int data;
Tree_Node *left;
Tree_Node *right;
Tree_Node(int x)
{
data = x;
left = NULL;
right = NULL;
}
};
// Inserting nodes at the beginning of the Linked List
void push_to_LL(struct LL_Node **head, int new_data)
{
struct LL_Node *new_node = new LL_Node(new_data);
new_node->next = *head;
*head = new_node;
}
// To perform inorder traversal of the created tree
void inorder_traversal(Tree_Node *root)
{
if (root)
{
inorder_traversal(root->left);
cout << root->data << " ";
inorder_traversal(root->right);
}
}
// To reverse Linked List
void reverse_LL(LL_Node **head)
{
LL_Node *prev = NULL;
LL_Node *cur = *head;
LL_Node *nxt;
while (cur != NULL)
{
nxt = cur->next;
cur->next = prev;
prev = cur;
cur = nxt;
}
*head = prev;
}
// To convert the Linked List to Binary Tree
void convert_LL_to_BinaryTree(LL_Node *head, Tree_Node *&root)
{
if (head == NULL)
return;
// create an empty queue
queue<Tree_Node *> q;
LL_Node *curr = head;
// create root of the tree
root = new Tree_Node(curr->data);
q.push(root);
// until the linked list is empty, run the while loop
while (curr->next != NULL)
{
Tree_Node *temp = q.front();
if (curr->next != NULL)
{
curr = curr->next;
// insert left child of tree
temp->left = new Tree_Node(curr->data);
// add it in the queue
q.push(temp->left);
}
if (curr->next != NULL)
{
curr = curr->next;
// insert right child of tree
temp->right = new Tree_Node(curr->data);
// add it in the queue
q.push(temp->right);
}
//remove the parent node from the queue
q.pop();
}
}
int main()
{
struct LL_Node *head = NULL;
push_to_LL(&head, 1);
push_to_LL(&head, 2);
push_to_LL(&head, 3);
push_to_LL(&head, 4);
push_to_LL(&head, 5);
push_to_LL(&head, 6);
// reverse the Linked List
reverse_LL(&head);
Tree_Node *root = NULL;
// construct the Binary Tree
cout<<"The inorder traversal of the binary tree is:"<<endl;
convert_LL_to_BinaryTree(head, root);
inorder_traversal(root);
return 0;
}

Input:

Output:

Time Complexity: O(n), as we are traversing through the whole linked list and doing level order traversal of the tree( which takes O(n) time). Here n refers to the number of nodes in the linked list.

Space Complexity: O(n), as we used a queue and created a binary tree with n nodes.

Frequently Asked Questions

How can a binary tree be represented using an array?

We can easily represent a binary tree using indexes of the array. If the index of a node is i, then its left child’s index will be ( 2*i + 1), and the index of its right child will be (2*i + 2).

How can a binary tree be represented using a linked list?

We can represent any binary tree using a linked list exactly similar to how we use arrays.

Why is the time complexity of the solution O(n)?

The time complexity of the solution is O(n) as we are traversing through the whole linked list and doing level order traversal of the tree.

Conclusion

In this blog, we learned how to approach and solve this question “Construct a Complete Binary Tree from its Linked List Representation”. It is a crucial question to help you clear your fundamentals concerning linked lists and trees.