Type like pro

# 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;

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

return null;
if(root.left!=null)
root.left.right=null;
if(root.right!=null)
root.right.left=null;
root.right=makeBst(root.right);
return root;
}