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

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 count =0;

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.*/
{
/*The first node is the head and last node*/
*last = temp;
}

else
{
(*last)->next = temp;
*last = temp;
}
}

/*Function that is used to print the Linked List*/
{
{
}
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
{

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;
b = a->next;
while(b != mid)
{
a = b;
b = a->next;
}
mid = mid->next;
newptr->right = LLtoBST(mid,ref_last,n-n/2-1);
return newptr;
}
}
}

/* Driver program to test above functions*/
int main()
{
last pointers to list*/
Lnode* last = NULL;

/*Inserts nodes at end of list*/

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

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 count =0;

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.*/
{
/*The first node is the head and last node*/
*last = temp;
}

else
{
(*last)->next = temp;
*last = temp;
}
}

/*Function that is used to print the Linked List*/
{
{
}
cout<<"NULL";
}

{
if(n<=0)
return NULL;

/*Recursively build left subtree*/

/*Create a root and link the left subtree with root*/
root->left = left;

/*Recursively build right subtree and link it with root*/

return root;
}

/* Driver program to test above functions*/
int main()
{
last pointers to list*/
Lnode* last = NULL;

/*Inserts nodes at end of list*/

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