  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Construct a Complete Binary Tree from its Linked List Representation

Last Updated on December 13, 2022 by Prepbytes This article discusses the most efficient approach to construct a binary tree using a linked list. Constructing binary trees from linked lists will definitely improve your data structures. Having knowledge about data structures like binary trees and linked lists is the most important part if you want to join the IT sector. Let’s discuss our topic “Construct binary tree using linked list” in detail.

## How To Make Binary Tree From Linked List

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.

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 child nodes 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 To Construct Binary Tree Using Linked List

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 To Construct Binary Tree Using Linked List

• 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 To Construct Binary Tree Using Linked List ## Code Implementation To Construct Binary Tree Using Linked List

```#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;

}

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

{

queue<node *=""> q;

{
root = NULL;
return;
}

q.push(root);

{

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

Node *leftChild = NULL, *rightChild = NULL;
q.push(leftChild);
{
q.push(rightChild);
}

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

void inorderTraversal(Node* root)
{
if (root)
{
inorderTraversal( root->left );
cout << root->data << " ";
inorderTraversal( root->right );
}
}

int main()
{

Node *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
{
BinaryTreeNode root;

void push(int new_data)
{

ListNode new_node = new ListNode(new_data);

}

BinaryTreeNode convertList2Binary(BinaryTreeNode node)
{

Queue<binarytreenode> q =

{
node = null;
return null;
}

{

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

BinaryTreeNode leftChild = null, rightChild = null;
{
}

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

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

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

class Conversion:

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

def push(self, new_data):

new_node = ListNode(new_data)

def convertList2Binary(self):

q = []

self.root = None
return

q.append(self.root)

parent = q.pop(0)
leftChild= None
rightChild = None
q.append(leftChild)
q.append(rightChild)
parent.left = leftChild
parent.right = rightChild

def inorderTraversal(self, root):
if(root):
self.inorderTraversal(root.left)
print (root.data,end=" ")
self.inorderTraversal(root.right)

conv = Conversion()
conv.push(36)
conv.push(30)
conv.push(23)
conv.push(13)
conv.push(12)
conv.push(10)
```
``````Output
Inorder Traversal of the constructed Binary Tree is
23 12 30 10 36 13``````

Space Complexity To Construct Binary Tree Using Linked List: O(n), the space required to create the binary tree.

This blog discussed in detail about how to construct binary tree using linked list. Data structures like binary trees and linked list always have a huge impact not only in interviews but also in real life. If you want to practice more questions on the linked list, you can follow this link Linked List.

## FAQ

1. What are the 4 types of linked list?
There are four key types of linked lists: