Given a Sorted Singly Linked List Array, Convert it into a Balanced Binary search Tree.

Given a Sorted Array, Convert it into its Balanced Binary search TreeObjective: You have been given a sorted singly List, you need to convert it into balanced binary search tree.

Why balanced binary tree is important:

You can also create the first node as root and insert all other nodes to the right of the tree because List is in increasing order but this constructed tree won’t be a balanced tree, it will be the skewed tree and to perform operations on this tree will be O(n), not O(logn).

Input: An sorted Singly Linked List

Output: Balanced Binary Tree

Example:

Singly Linked List To BST
Singly Linked List To BST

Approach:

  • Say mid is the middle node in the linked list.
  • Recursively construct left subtree from start to mid-1
  • Make the middle node as root and assign the left subtree to it.
  • Recursively construct the right subtree from mid+1 to end.
  • Assign the right subtree to root.

NOTE: This problem is very similar to “ Given a Sorted Array, Convert it into its Balanced Binary search Treeand Convert a Sorted Doubly Linked List to Balanced BST

Complete Code:

public class SortedLLToBST {
public static Node head = null;
public BSTNode LLToBST(int start, int end){
if(start>end)return null;
int mid = (start+end)/2;
BSTNode leftChild = LLToBST(start,mid1);
BSTNode root = new BSTNode(head.data);
root.left = leftChild;
head = head.next;
root.right = LLToBST(mid+1,end);
return root;
}
public int getSize(){
Node curr = head;
int size =0;
while(curr!=null){
curr=curr.next;
size++;
}
return size;
}
public void inorder(BSTNode root){
if(root!=null){
inorder(root.left);
System.out.print(" " + root.data);
inorder(root.right);
}
}
public static void main (String[] args) throws java.lang.Exception
{
head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(5);
Node tail = new Node(6);
head.next.next.next.next.next = tail;
SortedLLToBST i = new SortedLLToBST();
BSTNode x = i.LLToBST(1,i.getSize()) ;
System.out.print("Constructed BST is :");
i.inorder(x);
}
}
class Node{
int data;
Node next;
public Node(int data){
this.data = data;
next = null;
}
}
class BSTNode{
int data;
BSTNode left;
BSTNode right;
public BSTNode(int data){
this.data = data;
left = null;
right = null;
}
}

view raw
SortedLLToBST.java
hosted with ❤ by GitHub

Output:

Constructed BST is : 1 2 3 4 5 6