Convert sorted Linked List to balanced BST

In this post , we will see how to convert sorted LinkedList to balanced binary search tree.
There are two ways to do it.

Solution 1:

It is very much similar to convert sorted array to BST. Find middle element of linked list and make it root and do it recursively.
Time complexity : o(nlogn).

Solution 2:

This solution will follow bottom up approach rather than top down.

  • We need to find length of linked list
  • We will first create left subtree recursively using n/2 nodes.
  • We will create root node and connect left subtree to the root node.
  • Similarly create right subtree recursively and connect root to right subtree.

Java Program to convert sorted LinkedList to balanced BST:

When you run above program, you will get below output:

Time complexity : o(N).

Add Comment