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.

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).