Construct a Complete Binary Tree from its Linked List Representation

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

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

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

Run Code

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. 

Recommended Reading: 

• Introduction to C++
• Binary Tree vs Binary Search Tree
• Binary Tree Postorder Traversal
• Boundary Traversal of Binary Tree
• Top Trees Interview Questions
• DFS Algorithm
• Types of Binary Trees
• BFS v/s DFS in Binary Trees
• Binary Tree Interview Questions

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy learning, Ninja!