Sorted Linked List to balanced Binary Search Tree

By | April 17, 2016

Sorted Linked List to balanced Binary Search Tree (BST).

Problem statement to create a Binary Search Tree from a sorted linked list.

Given a singly linked list in a sorted order, create a balanced binary search tree (BST).

Example:

INPUT: Linked List: 1->5->8->10->12->15->20
OUTUT:
              10
           /     \
           5      15
         /  \    /  \
        1   8   12   20

Create a Binary Search Tree from a linked list Solution:

Method 1: Brute Force (naive) approach using divide and conquer:-

  1. Make the middle element root.
  2. Recur for right and left halves.
    1.Get the middle element of left half and make it left child of root created in step 1.
    2.Get the middle element of right half and make it right child of root created in step 1.
  3. Do this for all elements.

Solution code in C++ to build Binary Search Tree from sorted linked list:

#include <bits/stdc++.h>
#include<iostream>
using namespace std;
 
/*Standard structure that defines the node*/
struct Lnode
{
   int data;
   Lnode * next;
};
 
/*A Binary Search Tree node*/
struct Tnode
{
   int data;
   Tnode *left;
   Tnode *right;
};
 
/*Function to create a new binary search tree node*/
Tnode *newNode(int key)
{
   Tnode *temp=new Tnode;
   temp->data = key;
   temp->left = NULL;
   temp->right = NULL;
   return temp;
}
 
/*Function to print inorder traversal of BST*/
void inorder(Tnode *root)
{
   if(!root)
      return;
 
   inorder(root->left);
   cout<<root->data<<" ";
   inorder(root->right);
}
 
/*Function to count nodes in the linked list*/
int countNodes(Lnode *head)
{
   int count =0;
   Lnode *temp = head; 
 
   while(temp)
   {
      count++;
      temp = temp->next;
   }
 
   return count;
}
 
/*Function inserts nodes at end of Linked List*/
void Insert(Lnode **head, Lnode **last, int data)
{
    Lnode *temp = new Lnode;
    temp->data = data;
    temp->next = NULL;
 
    /*If list is empty.*/
    if(*head == NULL)
    {
        /*The first node is the head and last node*/
        *head = temp; 
        *last = temp;
    }
 
    else
    {
    	(*last)->next = temp;
    	*last = temp;
    }
}
 
/*Function that is used to print the Linked List*/
void printList(Lnode *head)
{
  while (head != NULL)
  {
     cout<<head->data<<"-> ";
     head = head->next;
  }
  cout<<"NULL";
}

/*Function to convert sorted linked list to BST*/
Tnode* LLtoBST(Lnode *ref_head,  Lnode* ref_last,int n)
{
    Tnode* newptr = NULL;
    
    if(n <= 0)
       return NULL;
    
    else 
    {
    	
        Lnode* mid = ref_head;
    	int count = 0;
        
         while(count)
         {
   	      count++;
              mid = mid->next;
         }
    	
         newptr = new Tnode;
    	 newptr->data = mid->data;
    	 if(n==1)
         {
              newptr->left = NULL;
    	      newptr->right = NULL;
    	      return newptr;
        }
   
        else
        {
              Lnode* a;
              Lnode* b;
              a = ref_head;
              b = a->next;
              while(b != mid)
              {
                   a = b;
                   b = a->next;
              }
    	      newptr->left = LLtoBST(ref_head,a,n/2);
    	      mid = mid->next;
    	      newptr->right = LLtoBST(mid,ref_last,n-n/2-1);
    	      return newptr;
         }
     }
}
 
/* Driver program to test above functions*/
int main()
{
    /*initialising head and 
    last pointers to list*/
    Lnode* head = NULL;
    Lnode* last = NULL;
    
    /*Inserts nodes at end of list*/
    Insert(&head, &last, 1);
    Insert(&head, &last, 5);
    Insert(&head, &last, 10);
    Insert(&head, &last, 20);
    Insert(&head, &last, 30);
    Insert(&head, &last, 40);
    Insert(&head, &last, 50); 
    Insert(&head, &last, 60);
 
    cout<<"Created Linked list is:\n";
    printList(head);
 
   int n = countNodes(head);
   
 
    /*Convert Linked List to BST*/
    Tnode*root=LLtoBST(head,last,n);
    
 
    cout<<"\n\nInorder traversal of binary search tree is:\n";
    inorder(root);
    
 
    return 0;
}

 

Output:

Created Linked list is:
1-> 5-> 10-> 20-> 30-> 40-> 50-> 60-> NULL

Inorder traversal of binary search tree is:
1 5 10 20 30 40 50 60

 

Time Complexity:O(nlogn)
where n is the number of nodes in linked list.


Method 2:

This method constructs the tree from leaves to the root. The nodes of linked list are taken in the same order so as to construct the tree in O(n) time complexity.

Algorithm for creating a Binary Search Tree from preorder traversal:

  1. Count the number of nodes in linked list.Let this number be n.
  2. Take n/2 left nodes and recursively build the left subtree.
  3. Allocate a root and link it to the left subtree.
  4. Recursively build the right subtree with remaining nodes i.e. n -1-n/2( subtract 1 for root node and n/2 for left subtree).
  5. Link it to the root node as well.
  6. Print the tree in a preorder traversal.

Solution code in C++ to build Binary Search Tree from sorted linked list:

#include <bits/stdc++.h>
using namespace std;
 
/*Standard structure that defines the node*/
struct Lnode
{
   int data;
   Lnode * next;
};

/*A Binary Search Tree node*/
struct Tnode
{
   int data;
   Tnode *left;
   Tnode *right;
};

/*Function to create a new binary search tree node*/
Tnode *newNode(int key)
{
   Tnode *temp=new Tnode;
   temp->data = key;
   temp->left = NULL;
   temp->right = NULL;
   return temp;
}

/*Function to print inorder traversal of BST*/
void inorder(Tnode *root)
{
   if(!root)
      return;
      
   preorder(root->left);
   cout<<root->data<<" "; 
   preorder(root->right);
}
 
/*Function to count nodes in the linked list*/
int countNodes(Lnode *head)
{
   int count =0;
   Lnode *temp = head; 
   
   while(temp)
   {
      count++;
      temp = temp->next;
   }
   
   return count;
}

/*Function inserts nodes at end of Linked List*/
void Insert(Lnode **head, Lnode **last, int data)
{
    Lnode *temp = new Lnode;
    temp->data = data;
    temp->next = NULL;
 
    /*If list is empty.*/
    if(*head == NULL)
    {
        /*The first node is the head and last node*/
        *head = temp; 
        *last = temp;
    }
 
    else
    {
    	(*last)->next = temp;
    	*last = temp;
    }
}

/*Function that is used to print the Linked List*/
void printList(Lnode *head)
{
  while (head != NULL)
  {
     cout<<head->data<<"-> ";
     head = head->next;
  }
  cout<<"NULL";
}
 
Tnode *LLtoBST(Lnode **ref_head,int n) 
{
   if(n<=0)
      return NULL;
      
   /*Recursively build left subtree*/
   Tnode *left = LLtoBST(ref_head,n/2);
   
   /*Create a root and link the left subtree with root*/
   Tnode *root = newNode((*ref_head)->data);
   root->left = left;
   
   /*Increment head pointer*/
   *ref_head = (*ref_head)->next;
   
   /*Recursively build right subtree and link it with root*/
   root->right = LLtoBST(ref_head, n-1-n/2);
   
   return root;
}
 
/* Driver program to test above functions*/
int main()
{
    /*initialising head and 
    last pointers to list*/
    Lnode* head = NULL;
    Lnode* last = NULL;
 
    /*Inserts nodes at end of list*/
    Insert(&head, &last, 1);
    Insert(&head, &last, 5);
    Insert(&head, &last, 10);
    Insert(&head, &last, 20);
    Insert(&head, &last, 30);
    Insert(&head, &last, 40);
    Insert(&head, &last, 50); 
    Insert(&head, &last, 60);

    cout<<"Created Linked list is:\n";
    printList(head);
  
   int n = countNodes(head);
   
    /*Convert Linked List to BST*/
    Tnode *root = LLtoBST(&head,n);

    cout<<"\n\nInorder traversal of binary search tree is:\n";
    preorder(root);
  
    return 0;
}

Output:

Created Linked list is:
1-> 5-> 10-> 20-> 30-> 40-> 50-> 60-> NULL

Inorder traversal of binary search tree is:
1 5 10 10 30 40 50 60

Time Complexity: O(n)