Queue: Given a Linked list, construct a complete binary tree

Problem Statement:

You are given a LL of a complete binary tree.

You need to construct complete binary tree.

If the root node is stored at position i, its left and right children are sorted at 2*i+1 and 2*i+2 respectively.

Example:

Solution Explanation:

Do level order traversal and built a tree using queue by traversing LL.

Head of the LL is always the root of the tree.

First node as root, then next 2 nodes are left and right children of the root.

So we take a parent node from the queue and make 2 nodes of the LL as children of the parent node and push the next 2 nodes into the queue.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <queue>
using namespace std;

class LLnode 
{
public:
    int data;
    LLnode* next;

    LLnode(int value) 
    {
        data = value;
        next = NULL;
    }
};

class TreeNode 
{
public:
    int data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int value) 
    {
        data = value;
        left = right = NULL;
    }
};


TreeNode* convertLLtoTree(LLnode* head) 
{

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

    queue<TreeNode*> q;

    TreeNode* root = new TreeNode(head->data);
    q.push(root);

    head = head->next;

    while (head) 
    {
      
        TreeNode* parent = q.front();
        q.pop();

        TreeNode* leftChild = NULL;
        TreeNode* rightChild = NULL;

        if (head) 
        {
            leftChild = new TreeNode(head->data);
            q.push(leftChild);
            head = head->next;
        }

        if (head) 
        {
            rightChild = new TreeNode(head->data);
            q.push(rightChild);
            head = head->next;
        }

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

    return root;
}

// Level Order Traversal 

void printTree(TreeNode* root) 
{

    if (root == NULL) 
    {
        return;
    }

    queue<TreeNode*> q;
    q.push(root);

    while (!q.empty()) 
    {
        TreeNode* currNode = q.front();
        q.pop();

        cout << currNode->data << " ";

        if (currNode->left) 
        {
            q.push(currNode->left);
        }
        if (currNode->right) 
        {
            q.push(currNode->right);
        }
    }
}

int main() 
{
  
    // Create linked list : 10->12->15->25->30->36
    LLnode* head = new LLnode(10);
    head->next = new LLnode(12);
    head->next->next = new LLnode(15);
    head->next->next->next = new LLnode(25);
    head->next->next->next->next = new LLnode(30);
    head->next->next->next->next->next = new LLnode(36); 
  
    TreeNode* root = convertLLtoTree(head);
    printTree(root);

    return 0;
}

Output

10 12 15 25 30 36