**Objective:** Given a sorted doubly linked list, convert it into Balanced binary search tree

**Input:** A Doubly Linked List

**Example:**

DLL TO BST Example

**Approach:**

- Get the size of the Doubly Linked list.
- Take left n/2 nodes and recursively construct left subtree
- Make the middle node as root and assign the left subtree( constructed in step 2) to root’s left.
- Recursively construct right subtree and link it to the the right of root made in step 3.
- See picture below

Doubly Linked List TO BST – Output

**Complete Code:**

**Output :**

DLL is :
1 2 3 4 5 6 7 8 9
Inorder traversal of contructed BST
1 2 3 4 5 6 7 8 9

__________________________________________________

**Top Companies Interview Questions..-**

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.

__________________________________________________

### Like this:

Like Loading...

*Related*