# 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

**moves one step ahead of where the**

*slow pointer***moves two-step at a time. Thus when the**

*fast pointer***reaches the end of the list, the**

*fast pointer***is at the midway.**

*slow pointer*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).

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.