How to convert sorted Linked List to balanced Binary Search Tree?

By | June 22, 2020

In this post, we will talk and learn about How to convert sorted LinkedList to a balanced binary search tree (BST).

Here I will talk about a couple of approaches:

The logic Used in this Program:

In this approach first, we find the middle element of LinkedList and make it root and do it recursively.
Time complexity: o(nlogn).

This solution usually follows a bottom-up approach rather than top-down.

  • First, we find the length of LinkedList
  • Afterward, we create the left subtree recursively using n/2 nodes.
  • Then we will create the root node and connect the left subtree to the root node.
  • Finally, we create the right subtree recursively and connect root to the right subtree.

Below Program is

Output of this program:

Printing LinkedList::
10 20 30 40 50 60 70
PreOrder traversal of binary search tree(BST) :
40 20 10 30 60 50 70

You May Also Like:

That’s all about How to convert sorted Linked List to balanced Binary Search Tree?
If you have any feedback or suggestion please feel free to drop in below comment box.

Leave a Reply

Your email address will not be published.