Home »
Data Structure
Construct a binary search tree from a sorted linked list
In this article, we are going to see how to create a binary search tree from a sorted single linked list?
Submitted by Radib Kar, on September 22, 2020
In this article, we are going to see how we can create a height-balanced binary Search tree from a given sorted linked list. Pay attention to the word "height-balanced" as it plays a huge role. We can create a binary search tree with the list by just creating a skew tree, where we will just put the list nodes as a right child only. For example,
Let's say the sorted list is: 1->2->3->4->5
Then the skew tree that can be created from this would be:
Though this is a Binary Search tree, it's not what we are expecting as it's not height-balanced. For a height-balanced tree, the difference between the left & right subtree will be maximum 1. So below is the approach to create a height-balanced binary search tree from a sorted linked list.
- Find the middle of the sorted list( Can be done with Floyd's hair & tortoise algorithm which uses a slow pointer & a fast pointer)
- The middle node is the root, left part of the middle node is the left subtree & right part is the right subtree
- Recursively construct left subtree & right subtree.
To find the middle of the linked list
We use Floyd's tortoise & hare algorithm for partitioning the linked list into two halves. We declare a slow pointer and a fast pointer. The slow pointer moves one step ahead of where the fast pointer moves two-step at a time. Thus when the fast pointer reaches the end of the list, the slow pointer is at the midway.
slow=head;
fast=head;
while(fast->next){
//move one step
slow=slow->next;
//move two steps if possible
fast=fast->next;
if(fast->next)
fast=fast->next;
}
//reach previous node to thee slow pointer to
//delink the left part of the slow pointer
ListNode* temp=head;
while(temp->next!=slow){
temp=temp->next;
}
//delink
temp->next=NULL;
To illustrate the algorithm visually, below is the step by step pictorial representation:
Firstly the list is 1->2->3->4->5->NULL
So we find the middle and de-link the left & right part and create a root node from the middle node of the sorted linked list.
Now we recursively create the left subtree
Now 1->NULL a single node and that would return a leaf node in the tree whereas NULL will be NULL in the tree as well. So after constructing the left subtree the semi-constructed BST would be:
Now, creating the right subtree similarly,
Then finally the BST would be:
N.B: this a height-balanced BST, but not only one. You can create another BST out of this which is still height-balanced and that would be like below:
Actually, it's due to the middle element we are picking up. In case of an odd length list, there is no problem, but in case of an even list there is two middle elements and based on which one we pick, there can be many such combinations. In our implementation, we have always chosen the second middle element in case of an even list as our middle element to create the root.
Below is the C++ implementation:
#include <bits/stdc++.h>
using namespace std;
// tree node is defined
class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int data)
{
val = data;
left = NULL;
right = NULL;
}
};
class ListNode {
public:
int val;
ListNode* next;
ListNode(int data)
{
val = data;
next = NULL;
}
};
void inorder(TreeNode* root)
{
if (!root)
return;
inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}
TreeNode* sortedListToBST(ListNode* head)
{
//base cases
//1.NULL list
if (!head)
return NULL;
//2. single node list
if (!head->next)
return new TreeNode(head->val);
//find the middle of the linked list
//using floyd's hair & tortoise algorithm
ListNode* slow = head;
ListNode* fast = head;
while (fast->next) {
//slow pointer moves one step at each iteration
slow = slow->next;
//fast pointer moves two steps at each iteration
fast = fast->next;
//this checking ensures that the 2nd move is possible
if (fast->next)
fast = fast->next;
}
//reach the previous node of the current slow pointer
ListNode* temp = head;
while (temp->next != slow) {
temp = temp->next;
}
//delink the left part of slow pointer(middle of the list)
temp->next = NULL;
//create root with the middle node
TreeNode* root = new TreeNode(slow->val);
//right part of the middle node
ListNode* ptr = slow->next;
//delink the right part
slow->next = NULL;
//recursively create left subtree from the left part
root->left = sortedListToBST(head);
//recursively create left subtree from the right part
root->right = sortedListToBST(ptr);
return root;
}
int main()
{
//building the tree like the example
ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(4);
head->next->next->next->next = new ListNode(5);
cout << "Creating self-balancing BST from the sorted list\n";
TreeNode* root = sortedListToBST(head);
cout << "height balanced BST created ...\n";
cout << "root of the BST created is: " << root->val << endl;
cout << "Inorder traversal of the BST\n";
inorder(root);
cout << endl;
return 0;
}
Output:
Creating self-balancing BST from the sorted list
height balanced BST created ...
root of the BST created is: 3
Inorder traversal of the BST
1 2 3 4 5
Dry run two show how Floyd's hair & tortoise works
Iteration 0 (Initially):
Iteration 1:
Iteration 2:
Iteration 3:
So now wherever slow pointer points that' our middle node which is 3 here
Now to delink the left part & right part we traverse a temp to the previous node of slow and then delink the left part & delinking right part is as simple as slow->next=NULL after we save the right part to some other pointer (otherwise we will lose the right part).
