Construct a Complete Binary Tree from its Linked List Representation

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

In this question, we are given the level order traversal of a binary tree, in the form of a linked list. We have to construct the complete binary tree from its linked list representation.

Problem Statement Understanding

Suppose the given linked list is 10 -> 12 -> 13 -> 23 -> 30 -> 36. For each ith node, its children are the (2i+1)th and (2i+2)nd nodes of the list. So, the children of 10 are 12 and 13. The children of 12 are 23 and 30. The children of 13 are 36 and NULL. All other nodes children's are NULL. Hence, the complete binary tree is :-

Input:

Output:

Explanation: As we can see, the output has a complete binary tree that has been created from its linked list representation.

This is a very interesting problem. We have to keep in mind that if the index of the root node is x (using 0 based indexing), then its left and right children are stored at the indices 2x+1 and 2x+2. We cannot directly access the nodes, so we have to traverse through the linked list. Let us have a glance at the approach.

Approach

What will be the root of the binary tree? The head. Yes, the head will be the root of the binary tree, as we are given the level order traversal. As we now know the root of the tree, we also know that the next two nodes of the linked list are the left and right children of the root.

So, now we know the partial binary tree. We are going to do a level order traversal of the binary tree using a queue and traverse the given linked list at the same time.

At every step, we will pick one node from the queue, and make the next two nodes of the linked list the children of the current(parent) node. After this, we are going to enqueue the next two nodes to the queue.

Algorithm

  • Base Case - If the head is NULL, then make the root NULL.
  • Create a queue.
  • Enqueue the first node of the linked list, and make it the root.
  • Traverse through the list, and do the following
  • Dequeue a node from the queue. This node is the current parent. Add the next two nodes of the linked list as the children of the current node(parent).
    Now, enqueue the two nodes in the queue.
  • Continue this till the end of the linked list.

Dry Run

Code Implementation


#include 
#include 
#include 
using namespace std;

struct ListNode
{
    int data;
    ListNode* next;
};

struct Node
{
    int data;
    Node *left, *right;
};

void push(struct ListNode** head_ref, int new_data)
{
    // allocate node and assign data
    struct ListNode* new_node = new ListNode;
    new_node->data = new_data;

    new_node->next = (*head_ref);

    (*head_ref)    = new_node;
}

Node* newNode(int data)
{
    Node *temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

void convertList2Binary(ListNode head, Node &root)
{

    queue q;

    if (head == NULL)
    {
        root = NULL; 
        return;
    }

    root = newNode(head->data);
    q.push(root);

    head = head->next;

    while (head)
    {

        Node* parent = q.front();
        q.pop();

        Node *leftChild = NULL, *rightChild = NULL;
        leftChild = newNode(head->data);
        q.push(leftChild);
        head = head->next;
        if (head)
        {
            rightChild = newNode(head->data);
            q.push(rightChild);
            head = head->next;
        }

        parent->left = leftChild;
        parent->right = rightChild;
    }
}

void inorderTraversal(Node* root)
{
    if (root)
    {
        inorderTraversal( root->left );
        cout << root->data << " ";
        inorderTraversal( root->right );
    }
}
 
int main()
{
   
    struct ListNode* head = NULL;
    push(&head, 36);  
    push(&head, 30);
    push(&head, 23);
    push(&head, 13);
    push(&head, 12);
    push(&head, 10); 
 
    Node *root;
    convertList2Binary(head, root);
 
    cout << "Inorder Traversal of the constructed Binary Tree is: \n";
    inorderTraversal(root);
    return 0;
}


import java.util.*;

 class ListNode
{
    int data;
    ListNode next;
    ListNode(int d)
    {
        data = d;
        next = null;
    }
}


 class BinaryTreeNode
{
    int data;
    BinaryTreeNode left, right = null;
    BinaryTreeNode(int data)
    {
        this.data = data;
        left = right = null;
    }
}

public class BinaryTree
{
    ListNode head;
    BinaryTreeNode root;

    void push(int new_data)
    {

        ListNode new_node = new ListNode(new_data);

        new_node.next = head;

        head = new_node;
    }

    BinaryTreeNode convertList2Binary(BinaryTreeNode node)
    {

        Queue q =
                    new LinkedList();


        if (head == null)
        {
            node = null;
            return null;
        }

        node = new BinaryTreeNode(head.data);
        q.add(node);


        head = head.next;

        while (head != null)
        {

            BinaryTreeNode parent = q.peek();
            BinaryTreeNode pp = q.poll();

            BinaryTreeNode leftChild = null, rightChild = null;
            leftChild = new BinaryTreeNode(head.data);
            q.add(leftChild);
            head = head.next;
            if (head != null)
            {
                rightChild = new BinaryTreeNode(head.data);
                q.add(rightChild);
                head = head.next;
            }

            parent.left = leftChild;
            parent.right = rightChild;
        }
        
        return node;
    }

    void inorderTraversal(BinaryTreeNode node)
    {
        if (node != null)
        {
            inorderTraversal(node.left);
            System.out.print(node.data + " ");
            inorderTraversal(node.right);
        }
    }

    public static void main(String[] args)
    {
        BinaryTree tree = new BinaryTree();
        tree.push(36); 
        tree.push(30);
        tree.push(23);
        tree.push(13);
        tree.push(12);
        tree.push(10); 
        BinaryTreeNode node = tree.convertList2Binary(tree.root);

        System.out.println("Inorder Traversal of the"+
                        " constructed Binary Tree is:");
        tree.inorderTraversal(node);
    }
}

Output

Inorder Traversal of the constructed Binary Tree is
23 12 30 10 36 13

Space Complexity: O(n), the space required to create the binary tree.

So, in this article, we have tried to explain the most efficient approach to construct a complete binary tree from its linked list representation. This is an important question when it comes to coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Remove the last node of a linked list
Next post Given a Linked List which is sorted, how to insert in a sorted way

Leave a Reply

Your email address will not be published. Required fields are marked *