Construct Complete Binary Tree from its Linked List Representation

Last Updated : 13 Feb, 2023

Given Linked List Representation of Complete Binary Tree, construct the Binary tree. A complete binary tree can be represented in an array in the following approach.
If the root node is stored at index i, its left, and right children are stored at indices 2*i+1, and 2*i+2 respectively.
Suppose a tree is represented by a linked list in the same way, how do we convert this into a normally linked representation of a binary tree where every node has data, left and right pointers? In the linked list representation, we cannot directly access the children of the current node unless we traverse the list.

LinkedListToBST

We are mainly given level order traversal in sequential access form. We know head of linked list is always is root of the tree. We take the first node as root and we also know that the next two nodes are left and right children of root. So we know partial Binary Tree. The idea is to do Level order traversal of the partially built Binary Tree using queue and traverse the linked list at the same time. At every step, we take the parent node from queue, make next two nodes of linked list as children of the parent node, and enqueue the next two nodes to queue.
1. Create an empty queue.
2. Make the first node of the list as root, and enqueue it to the queue.
3. Until we reach the end of the list, do the following.
………a. Dequeue one node from the queue. This is the current parent.
………b. Traverse two nodes in the list, add them as children of the current parent.
………c. Enqueue the two nodes into the queue.

Below is the implementation of the above approach:

C++

// C++ program to create a Complete Binary tree from its Linked List
// Representation
#include <iostream>
#include <string>
#include <queue>
using namespace std;
 
// Linked list node
struct ListNode
{
    int data;
    ListNode* next;
};
 
// Binary tree node structure
struct BinaryTreeNode
{
    int data;
    BinaryTreeNode *left, *right;
};
 
// Function to insert a node at the beginning of the Linked List
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;
 
    // link the old list of the new node
    new_node->next = (*head_ref);
 
    // move the head to point to the new node
    (*head_ref)    = new_node;
}
 
// method to create a new binary tree node from the given data
BinaryTreeNode* newBinaryTreeNode(int data)
{
    BinaryTreeNode *temp = new BinaryTreeNode;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
 
// converts a given linked list representing a complete binary tree into the
// linked representation of binary tree.
void convertList2Binary(ListNode *head, BinaryTreeNode* &root)
{
    // queue to store the parent nodes
    queue<BinaryTreeNode *> q;
 
    // Base Case
    if (head == NULL)
    {
        root = NULL; // Note that root is passed by reference
        return;
    }
 
    // 1.) The first node is always the root node, and add it to the queue
    root = newBinaryTreeNode(head->data);
    q.push(root);
 
    // advance the pointer to the next node
    head = head->next;
 
    // until the end of linked list is reached, do the following steps
    while (head)
    {
        // 2.a) take the parent node from the q and remove it from q
        BinaryTreeNode* parent = q.front();
        q.pop();
 
        // 2.c) take next two nodes from the linked list. We will add
        // them as children of the current parent node in step 2.b. Push them
        // into the queue so that they will be parents to the future nodes
        BinaryTreeNode *leftChild = NULL, *rightChild = NULL;
        leftChild = newBinaryTreeNode(head->data);
        q.push(leftChild);
        head = head->next;
        if (head)
        {
            rightChild = newBinaryTreeNode(head->data);
            q.push(rightChild);
            head = head->next;
        }
 
        // 2.b) assign the left and right children of parent
        parent->left = leftChild;
        parent->right = rightChild;
       
          
    }
}
 
// Utility function to traverse the binary tree after conversion
void inorderTraversal(BinaryTreeNode* root)
{
    if (root)
    {
        inorderTraversal( root->left );
        cout << root->data << " ";
        inorderTraversal( root->right );
    }
}
 
// Driver program to test above functions
int main()
{
    // create a linked list shown in above diagram
    struct ListNode* head = NULL;
    push(&head, 36);  /* Last node of Linked List */
    push(&head, 30);
    push(&head, 25);
    push(&head, 15);
    push(&head, 12);
    push(&head, 10); /* First node of Linked List */
 
    BinaryTreeNode *root;
    convertList2Binary(head, root);
 
    cout << "Inorder Traversal of the constructed Binary Tree is: \n";
    inorderTraversal(root);
    return 0;
}

Java

// Java program to create complete Binary Tree from its Linked List
// representation
  
// importing necessary classes
import java.util.*;
  
// A linked list node
class ListNode 
{
    int data;
    ListNode next;
    ListNode(int d)
    {
        data = d;
        next = null;
    }
}
  
// A binary tree node
class BinaryTreeNode 
{
    int data;
    BinaryTreeNode left, right = null;
    BinaryTreeNode(int data)
    {
        this.data = data;
        left = right = null;
    }
}
  
class BinaryTree 
{
    ListNode head;
    BinaryTreeNode root;
  
    // Function to insert a node at the beginning of
    // the Linked List
    void push(int new_data) 
    {
        // allocate node and assign data
        ListNode new_node = new ListNode(new_data);
  
        // link the old list of the new node
        new_node.next = head;
  
        // move the head to point to the new node
        head = new_node;
    }
  
    // converts a given linked list representing a 
    // complete binary tree into the linked 
    // representation of binary tree.
    BinaryTreeNode convertList2Binary(BinaryTreeNode node) 
    {
        // queue to store the parent nodes
        Queue<BinaryTreeNode> q = 
                       new LinkedList<BinaryTreeNode>();
  
        // Base Case
        if (head == null) 
        {
            node = null; 
            return null;
        }
  
        // 1.) The first node is always the root node, and
        //     add it to the queue
        node = new BinaryTreeNode(head.data);
        q.add(node);
  
        // advance the pointer to the next node
        head = head.next;
  
        // until the end of linked list is reached, do the
        // following steps
        while (head != null) 
        {
            // 2.a) take the parent node from the q and 
            //      remove it from q
            BinaryTreeNode parent = q.peek();
              
            // 2.c) take next two nodes from the linked list.
            // We will add them as children of the current 
            // parent node in step 2.b. Push them into the
            // queue so that they will be parents to the 
            // future nodes
            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;
            }
  
            // 2.b) assign the left and right children of
            //      parent
            parent.left = leftChild;
            parent.right = rightChild;
           
              //remove current level node
              q.poll();
        }
          
        return node;
    }
  
    // Utility function to traverse the binary tree 
    // after conversion
    void inorderTraversal(BinaryTreeNode node) 
    {
        if (node != null) 
        {
            inorderTraversal(node.left);
            System.out.print(node.data + " ");
            inorderTraversal(node.right);
        }
    }
  
    // Driver program to test above functions
    public static void main(String[] args) 
    {
        BinaryTree tree = new BinaryTree();
        tree.push(36); /* Last node of Linked List */
        tree.push(30);
        tree.push(25);
        tree.push(15);
        tree.push(12);
        tree.push(10); /* First node of Linked List */
        BinaryTreeNode node = tree.convertList2Binary(tree.root);
  
        System.out.println("Inorder Traversal of the"+
                        " constructed Binary Tree is:");
        tree.inorderTraversal(node);
    }
}
// This code has been contributed by Mayank Jaiswal

Python3

# Python program to create a Complete Binary Tree from
# its linked list representation
 
# Linked List node
class ListNode:
 
        # Constructor to create a new node
        def __init__(self, data):
            self.data = data
            self.next = None
 
# Binary Tree Node structure
class BinaryTreeNode:
 
    # Constructor to create a new node
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
# Class to convert the linked list to Binary Tree
class Conversion:
 
    # Constructor for storing head of linked list
    # and root for the Binary Tree
    def __init__(self, data = None):
        self.head = None
        self.root = None
 
    def push(self, new_data):
 
        # Creating a new linked list node and storing data
        new_node = ListNode(new_data)
 
        # Make next of new node as head
        new_node.next = self.head
 
        # Move the head to point to new node
        self.head = new_node
 
    def convertList2Binary(self):
 
        # Queue to store the parent nodes
        q = []
 
        # Base Case
        if self.head is None:
            self.root = None
            return
 
        # 1.) The first node is always the root node,
        # and add it to the queue
        self.root = BinaryTreeNode(self.head.data)
        q.append(self.root)
 
        # Advance the pointer to the next node
        self.head = self.head.next
 
        # Until the end of linked list is reached, do:
        while(self.head):
 
            # 2.a) Take the parent node from the q and
            # and remove it from q
            parent = q.pop(0) # Front of queue
 
            # 2.c) Take next two nodes from the linked list.
            # We will add them as children of the current
            # parent node in step 2.b.
            # Push them into the queue so that they will be
            # parent to the future node
            leftChild= None
            rightChild = None
 
            leftChild = BinaryTreeNode(self.head.data)
            q.append(leftChild)
            self.head = self.head.next
            if(self.head):
                rightChild = BinaryTreeNode(self.head.data)
                q.append(rightChild)
                self.head = self.head.next
 
            #2.b) Assign the left and right children of parent
            parent.left = leftChild
            parent.right = rightChild
 
    def inorderTraversal(self, root):
        if(root):
            self.inorderTraversal(root.left)
            print (root.data,end=" ")
            self.inorderTraversal(root.right)
 
# Driver Program to test above function
 
# Object of conversion class
conv = Conversion()
conv.push(36)
conv.push(30)
conv.push(25)
conv.push(15)
conv.push(12)
conv.push(10)
 
conv.convertList2Binary()
 
print ("Inorder Traversal of the constructed Binary Tree is:")
conv.inorderTraversal(conv.root)
 
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

C#

// C# program to create complete 
// Binary Tree from its Linked List
// representation
 
// importing necessary classes
using System;
using System.Collections.Generic; 
 
// A linked list node
public class ListNode 
{
    public int data;
    public ListNode next;
    public ListNode(int d)
    {
        data = d;
        next = null;
    }
}
 
// A binary tree node
public class BinaryTreeNode 
{
    public int data;
    public BinaryTreeNode left, right = null;
    public BinaryTreeNode(int data)
    {
        this.data = data;
        left = right = null;
    }
}
 
public class BinaryTree 
{
    ListNode head;
    BinaryTreeNode root;
 
    // Function to insert a node at 
    // the beginning of the Linked List
    void push(int new_data) 
    {
        // allocate node and assign data
        ListNode new_node = new ListNode(new_data);
 
        // link the old list of the new node
        new_node.next = head;
 
        // move the head to point to the new node
        head = new_node;
    }
 
    // converts a given linked list representing a 
    // complete binary tree into the linked 
    // representation of binary tree.
    BinaryTreeNode convertList2Binary(BinaryTreeNode node) 
    {
        // queue to store the parent nodes
        Queue<BinaryTreeNode> q = 
                    new Queue<BinaryTreeNode>();
 
        // Base Case
        if (head == null) 
        {
            node = null; 
            return null;
        }
 
        // 1.) The first node is always the root node, and
        //     add it to the queue
        node = new BinaryTreeNode(head.data);
        q.Enqueue(node);
 
        // advance the pointer to the next node
        head = head.next;
 
        // until the end of linked list is reached,
        //  do the following steps
        while (head != null) 
        {
            // 2.a) take the parent node from the q and 
            //     remove it from q
            BinaryTreeNode parent = q.Peek();
            BinaryTreeNode pp = q.Dequeue();
             
            // 2.c) take next two nodes from the linked list.
            // We will add them as children of the current 
            // parent node in step 2.b. Push them into the
            // queue so that they will be parents to the 
            // future nodes
            BinaryTreeNode leftChild = null, rightChild = null;
             
            leftChild = new BinaryTreeNode(head.data);
            q.Enqueue(leftChild);
            head = head.next;
             
            if (head != null) 
            {
                rightChild = new BinaryTreeNode(head.data);
                q.Enqueue(rightChild);
                head = head.next;
            }
 
            // 2.b) assign the left and right children of
            //     parent
            parent.left = leftChild;
            parent.right = rightChild;
        }
         
        return node;
    }
 
    // Utility function to traverse the binary tree 
    // after conversion
    void inorderTraversal(BinaryTreeNode node) 
    {
        if (node != null) 
        {
            inorderTraversal(node.left);
            Console.Write(node.data + " ");
            inorderTraversal(node.right);
        }
    }
 
    // Driver code
    public static void Main() 
    {
        BinaryTree tree = new BinaryTree();
         
        /* Last node of Linked List */
        tree.push(36); 
        tree.push(30);
        tree.push(25);
        tree.push(15);
        tree.push(12);
         
        /* First node of Linked List */
        tree.push(10); 
        BinaryTreeNode node = tree.convertList2Binary(tree.root);
 
        Console.WriteLine("Inorder Traversal of the"+
                        " constructed Binary Tree is:");
        tree.inorderTraversal(node);
    }
}
 
/* This code is contributed PrinciRaj1992 */

Javascript

<script>
 
      // JavaScript program to create complete
      // Binary Tree from its Linked List
      // representation
 
      // importing necessary classes
      // A linked list node
      class ListNode {
        constructor(d) {
          this.data = d;
          this.next = null;
        }
      }
 
      // A binary tree node
      class BinaryTreeNode {
        constructor(data) {
          this.data = data;
          this.left = null;
          this.right = null;
        }
      }
 
      class BinaryTree {
        constructor() {
          this.head = null;
          this.root = null;
        }
 
        // Function to insert a node at
        // the beginning of the Linked List
        push(new_data) {
          // allocate node and assign data
          var new_node = new ListNode(new_data);
 
          // link the old list of the new node
          new_node.next = this.head;
 
          // move the head to point to the new node
          this.head = new_node;
        }
 
        // converts a given linked list representing a
        // complete binary tree into the linked
        // representation of binary tree.
        convertList2Binary(node) {
          // queue to store the parent nodes
          var q = [];
 
          // Base Case
          if (this.head == null) {
            node = null;
            return null;
          }
 
          // 1.) The first node is always the root node, and
          //     add it to the queue
          node = new BinaryTreeNode(this.head.data);
          q.push(node);
 
          // advance the pointer to the next node
          this.head = this.head.next;
 
          // until the end of linked list is reached,
          //  do the following steps
          while (this.head != null) {
            // 2.a) take the parent node from the q and
            //     remove it from q
 
            var parent = q.shift();
 
            // 2.c) take next two nodes from the linked list.
            // We will add them as children of the current
            // parent node in step 2.b. Push them into the
            // queue so that they will be parents to the
            // future nodes
            var leftChild = null,
              rightChild = null;
 
            leftChild = new BinaryTreeNode(this.head.data);
            q.push(leftChild);
            this.head = this.head.next;
 
            if (this.head != null) {
              rightChild = new BinaryTreeNode(this.head.data);
              q.push(rightChild);
              this.head = this.head.next;
            }
 
            // 2.b) assign the left and right children of
            //     parent
            parent.left = leftChild;
            parent.right = rightChild;
          }
 
          return node;
        }
 
        // Utility function to traverse the binary tree
        // after conversion
        inorderTraversal(node) {
          if (node != null) {
            this.inorderTraversal(node.left);
            document.write(node.data + " ");
            this.inorderTraversal(node.right);
          }
        }
      }
 
      // Driver code
      var tree = new BinaryTree();
 
      /* Last node of Linked List */
      tree.push(36);
      tree.push(30);
      tree.push(25);
      tree.push(15);
      tree.push(12);
 
      /* First node of Linked List */
      tree.push(10);
      var node = tree.convertList2Binary(tree.root);
 
      document.write(
     "Inorder Traversal of the" + " constructed Binary Tree is:<br>"
      );
      tree.inorderTraversal(node);
 
</script>

Output

Inorder Traversal of the constructed Binary Tree is: 
25 12 30 10 36 15

Time Complexity: O(n), where n is the number of nodes.
Auxiliary Space: O(b), Here b is the maximum number of nodes at any level.

This article is compiled by Ravi Chandra Enaganti.

GeeksforGeeks

Improve

Previous Article

Populate Inorder Successor for all nodes

Minimum swap required to convert binary tree to binary search tree

Similar Reads

Construct Full Binary Tree using its Preorder traversal and Preorder traversal of its mirror tree

Given two arrays that represent Preorder traversals of a full binary tree and its mirror tree, we need to write a program to construct the binary tree using these two Preorder traversals.A Full Binary Tree is a binary tree where every node has either 0 or 2 children. Note: It is not possible to construct a general binary tree using these two traver

Construct Binary Tree from given Parent Array representation | Iterative Approach

Given an array that represents a tree in such a way that array indexes are values in tree nodes and array values give the parent node of that particular index (or node). The value of the root node index would always be -1 as there is no parent for root. Construct the standard linked representation of given Binary Tree from this given representation

Construct a Binary Tree from String with bracket representation | Set 2

Given a string s consisting of parentheses {'(' and ')'} and integers, the task is to construct a Binary Tree from it and print its Preorder traversal. Examples: Input: S = "1(2)(3)"Output: 1 2 3Explanation: The corresponding binary tree is as follows: 1 / \ 2 3 Input: "4(2(3)(1))(6(5))"Output: 4 2 3 1 6 5Explanation:The corresponding binary tree i

Construct Binary Tree from String with bracket representation

Construct a binary tree from a string consisting of parenthesis and integers. The whole input represents a binary tree. It contains an integer followed by zero, one or two pairs of parenthesis. The integer represents the root's value and a pair of parenthesis contains a child binary tree with the same structure. Always start to construct the left c

Construct Binary Tree from given Parent Array representation

Given an array that represents a tree in such a way that array indexes are values in tree nodes and array values give the parent node of that particular index (or node). The value of the root node index would always be -1 as there is no parent for root. Construct the standard linked representation of given Binary Tree from this given representation

Convert a Binary Tree into its Mirror Tree (Invert Binary Tree)

Given a binary tree, the task is to convert the binary tree into its Mirror tree. Mirror of a Binary Tree T is another Binary Tree M(T) with left and right children of all non-leaf nodes interchanged. Recommended PracticeMirror TreeTry It!The idea is to traverse recursively and swap the right and left subtrees after traversing the subtrees. Follow

Linked complete binary tree & its creation

A complete binary tree is a binary tree where each level 'l' except the last has 2^l nodes and the nodes at the last level are all left-aligned. Complete binary trees are mainly used in heap-based data structures. The nodes in the complete binary tree are inserted from left to right in one level at a time. If a level is full, the node is inserted i

Construct a complete binary tree from given array in level order fashion

Given an array of elements, our task is to construct a complete binary tree from this array in a level order fashion. That is, elements from the left in the array will be filled in the tree level-wise starting from level 0.Examples: Input : arr[] = {1, 2, 3, 4, 5, 6}Output : Root of the following tree 1 / \ 2 3 / \ / 4 5 6Input: arr[] = {1, 2, 3, 4

Construct a Maximum Sum Linked List out of two Sorted Linked Lists having some Common nodes

Given two sorted linked lists, construct a linked list that contains maximum sum path from start to end. The result list may contain nodes from both input lists. When constructing the result list, we may switch to the other input list only at the point of intersection (which mean the two node with the same value in the lists). You are allowed to us

Construct a Doubly linked linked list from 2D Matrix

Given a 2D matrix, the task is to convert it into a doubly-linked list with four pointers that are next, previous, up, and down, each node of this list should be connected to its next, previous, up, and down nodes.Examples: Input: 2D matrix 1 2 3 4 5 6 7 8 9 Output: Approach: The main idea is to construct a new node for every element of the matrix

Article Tags :

Practice Tags :