Construct a Complete Binary Tree from its Linked List Representation

Debarati Ghatak
Last Updated: May 13, 2022

Introduction

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.

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 inorder traversal of the tree.

 

In typical array representation of a tree, if a node is stored at index, 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 child of the root node.

 

In our example test case,

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

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

So the root of the tree (1) has two children now - left child (2) and 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. 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 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 inorder traversal of the constructed tree is printed.

Steps of algorithm

  1. Create an empty queue.
  2. Create the root of the tree using the data part of the head of the given linked list.
  3. Enqueue the node.
  4. Run a while loop until we reach the last node of the linked list,
  5. Connect two nodes to the root node - the first one as the left child and the second as the right child.
  6. Enqueue the two nodes.
  7. Dequeue the current root node/parent node.

Pseudocode

Create empty queue q
curr <- head
root <- curr.data
q.enqueue(root)
while(curr.next)
{
temp <- q.front
curr <- curr.next
temp.left <- curr.data
q.enqueue(temp.left)
curr <- curr.next
temp.right <- curr.data
q.enqueue(temp.right)
q.dequeue
}

C++ Code

#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

Q1 How can a binary tree be represented using an array?

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

 

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

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

 

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

Ans: 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.

Key Takeaways

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. 

If you don’t know about the level order traversal of a binary tree, you should first learn it from here and then come back to this problem for better understanding.

Happy learning, Ninja!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think