## Thursday, May 5, 2022

### Question 75 : Convert sorted Linked List to balanced BST

In this post, we will see how to convert sorted LinkedList to a 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:

``````public class SortedLinkedListToBSTMain {

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);
}

} else {
while (temp.next != null)
temp = temp.next;

temp.next = node;
}
}

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

// Find length of linked list using iterative method
int count = 0;
while (temp != null) {
temp = temp.next;
count++;
}
return count;
}

/* Base Case for recursion*/
if (n <= 0)
return null;

/* Recursively creating the left subtree */
TreeNode left = convertSortedLinkedListToBST(n / 2);

/* Create a root node*/

// Set pointer to left subtree
root.left = left;
/* Create right subtree with remaining nodes*/
root.right = convertSortedLinkedListToBST(n - n / 2 - 1);

return root;
}
public static void main(String[] args) {

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

Don't miss the next article!
Be the first to be notified when a new article or Kubernetes experiment is published.

## You may also like

Kubernetes Microservices
Python AI/ML
Spring Framework Spring Boot
Core Java Java Coding Question
Maven AWS