Given a Sorted Singly Linked List Array, Convert it into a Balanced Binary search Tree.

Objective: You have been given a sorted singly List, you need to convert it into balanced binary search tree.

Why balanced binary tree is important:

You can also create first node as root and insert all other nodes to the right of the tree because List is in increasing order but this constructed tree won’t be balanced tree, it wil be skwed tree and to perform operations on this tree will be O(n) not O(logn).

Input: An sorted Singly Linked List

Output: Balanced Binary Tree


Singly Linked List To BST

Singly Linked List To BST


  • Say mid is the middle node in the linked list.
  • Recursively construct left subtree from start to mid-1
  • Make the middle node as root and assign the left subtree to it.
  • Recursively construct right subtree from mid+1 to end.
  • Assign the right subtree to root.

NOTE: This problem is very smililar to “ Given a Sorted Array, Convert it into its Balanced Binary search TreeandConvert a Sorted Doubly Linked List to Balanced BST” .

Complete Code:


Constructed BST is : 1 2 3 4 5 6

Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: