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:

package org.arpit.java2blog;

import org.arpit.java2blog.BinarySearchTreeMain.TreeNode;

public class SortedLinkedListToBSTMain {

 private Node head;
 
 private static class Node {
  private int value;
  private Node next;

  Node(int value) {
   this.value = value;

  }
 }

 public static class TreeNode {
  int data;
  TreeNode left;
  TreeNode right;

  TreeNode(int data) {
   this.data = data;
  }
 }

 public static void preOrder(TreeNode root) {
  if (root == null)
   return;
  System.out.print(root.data + " ");
  preOrder(root.left);
  preOrder(root.right);
 }
 
 public void addToTheLast(Node node) {

  if (head == null) {
   head = node;
  } else {
   Node temp = head;
   while (temp.next != null)
    temp = temp.next;

   temp.next = node;
  }
 }

 public void printList(Node head) {
  Node temp = head;
  while (temp != null) {
   System.out.format("%d ", temp.value);
   temp = temp.next;
  }
  System.out.println();
 }

 // Find length of linked list using iterative method
 public  int lengthOfLinkedList()
 {
  Node temp=head;
  int count = 0;
  while(temp!=null)
  {
   temp=temp.next;
   count++;  
  }
  return count;
 }
 
 public  TreeNode convertSortedLinkedListToBST(int n)
 {
   /* Base Case for recursion*/
        if (n <= 0) 
            return null;
 
        /* Recursively creating the left subtree */
        TreeNode left = convertSortedLinkedListToBST(n / 2);
 
        /* Create a root node*/
        TreeNode root = new TreeNode(head.value);
 
        // Set pointer to left subtree
        root.left = left;
        head = head.next;
        /* Create right subtree with remaining nodes*/
        root.right = convertSortedLinkedListToBST(n - n / 2 - 1);
 
        return root;
 }
 public static void main(String[] args) {
  SortedLinkedListToBSTMain list = new SortedLinkedListToBSTMain();
  // Creating a linked list
  Node head = new Node(10);
  list.addToTheLast(head);
  list.addToTheLast(new Node(20));
  list.addToTheLast(new Node(30));
  list.addToTheLast(new Node(40));
  list.addToTheLast(new Node(50));
  list.addToTheLast(new Node(60));
  list.addToTheLast(new Node(70));
  list.addToTheLast(new Node(80));
  list.addToTheLast(new Node(90));
  System.out.println("Printing linked list :");
  list.printList(head);
  int n =list.lengthOfLinkedList();
  
  TreeNode bst=list.convertSortedLinkedListToBST(n);
  System.out.println("---------------");
  System.out.println("Pre order traversal of binary search tree :");
  preOrder(bst);

 }

}
When you run above program, you will get below output:
Printing linked list :
10 20 30 40 50 60 70 80 90 
---------------
Pre order traversal of binary search tree :
50 30 20 10 40 80 70 60 90 
Time complexity : o(N).

Written by Arpit:

If you have read the post and liked it. Please connect with me on Facebook | Twitter | Google Plus

 

Java tutorial for beginners Copyright © 2012