Make BST from doubly linked list

Problem

You are given a sorted doubly linked list. Nodes of this doubly linked list have a left as previous and right as next pointer and a value. Convert this to a binary search tree using the same nodes. 

Solution

We will search for the middle of this doubly linked list and make that middle node as the root of Binary search tree. Then we will recursively construct its left and right subtree.

Code

package dsalgo;

public class MakeBSTFromDoublyLinkedList {

 static class Node{
  Node left;
  Node right;
  int value;
  Node(int value){
   this.value=value;
  }
 }
 public static void main(String[] args) {
  Node a=new Node(1);
  Node b=new Node(2);
  Node c=new Node(3);
  Node d=new Node(4);
  Node e=new Node(5);
  Node f=new Node(6);
  Node g=new Node(7);
  Node h=new Node(8);
  Node i=new Node(9);
  Node j=new Node(10);
  
  a.right=b;
  b.right=c;
  c.right=d;
  d.right=e;
  e.right=f;
  f.right=g;
  g.right=h;
  h.right=i;
  i.right=j;
  
  j.left=i;
  i.left=h;
  h.left=g;
  g.left=f;
  f.left=e;
  e.left=d;
  d.left=c;
  c.left=b;
  b.left=a;
  Node root=makeBst(a);
 }
 
 public static Node makeBst(Node head){
  if(head==null)
   return null;
  if(head.right==null)
  return head;
  Node root=findMiddle(head);
  if(root.left!=null)
   root.left.right=null;
  root.left=makeBst(head);
  if(root.right!=null)
   root.right.left=null;
  root.right=makeBst(root.right);
  return root;
 }
 public static Node findMiddle(Node head){
  if(head.right==null)
  return head; 
  Node firstPointer=head;
  while(firstPointer!=null){
   head=head.right;
   firstPointer=firstPointer.right;
   if(firstPointer==null)break;
   firstPointer=firstPointer.right;
   if(firstPointer==null)break;
   firstPointer=firstPointer.right;
  }
  return head;
 }
}