Construct a Complete Binary Tree from its Linked List Representation


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



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.


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.


  • 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 <iostream>
#include <string>
#include <queue>
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<node *=""> q;

    if (head == NULL)
        root = NULL; 

    root = newNode(head->data);

    head = head->next;

    while (head)

        Node* parent = q.front();

        Node *leftChild = NULL, *rightChild = NULL;
        leftChild = newNode(head->data);
        head = head->next;
        if (head)
            rightChild = newNode(head->data);
            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";
    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)
    { = data;
        left = right = null;

public class BinaryTree
    ListNode head;
    BinaryTreeNode root;

    void push(int new_data)

        ListNode new_node = new ListNode(new_data); = head;

        head = new_node;

    BinaryTreeNode convertList2Binary(BinaryTreeNode node)

        Queue<binarytreenode> q =
                    new LinkedList<binarytreenode>();

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

        node = new BinaryTreeNode(;

        head =;

        while (head != null)

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

            BinaryTreeNode leftChild = null, rightChild = null;
            leftChild = new BinaryTreeNode(;
            head =;
            if (head != null)
                rightChild = new BinaryTreeNode(;
                head =;

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

    void inorderTraversal(BinaryTreeNode node)
        if (node != null)
            System.out.print( + " ");

    public static void main(String[] args)
        BinaryTree tree = new BinaryTree();
        BinaryTreeNode node = tree.convertList2Binary(tree.root);

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

class ListNode:
        def __init__(self, data):
   = data
   = None

class Node:
    def __init__(self, data): = data
        self.left = None
        self.right = None

class Conversion:

    def __init__(self, data = None):
        self.head = None
        self.root = None

    def push(self, new_data):

        new_node = ListNode(new_data) = self.head
        self.head = new_node

    def convertList2Binary(self):

        q = []

        if self.head is None:
            self.root = None
        self.root = Node(
        self.head =
            parent = q.pop(0)
            leftChild= None
            rightChild = None
            leftChild = Node(
            self.head =
                rightChild = Node(
                self.head =
            parent.left = leftChild
            parent.right = rightChild

    def inorderTraversal(self, root):
            print (,end=" ")

conv = Conversion()


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

[forminator_quiz id="3687"]

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.

Leave a Reply

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