// Program to create a complete binary tree from a 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(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 off 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
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);
getchar();
return 0; 
}