This is one of the difficult linked list questions you will find on interviews. You need to write a program to convert a given doubly Linked, which is sorted in ASCENDING order to construct a Balanced Binary Search Tree which has same the values as the given doubly linked list. The challenge is usually increased by PUTTING a restriction to construct the BST in-place i.e. no new node should be allocated for tree conversion)

INPUT: A Doubly linked list 10 20 30 40 50 60 70

Output: A balanced binary search tree BST

40

/

20 60

/ /

 10 30 40 70

This is one of the difficult linked list questions you will find on interviews. You need to write a program to convert a given doubly Linked, which is sorted in ascending order to construct a Balanced Binary Search Tree which has same the values as the given doubly linked list. The challenge is usually increased by putting a restriction to construct the BST in-place i.e. no new node should be allocated for tree conversion)

Input: A Doubly linked list 10 20 30 40 50 60 70

Output: A balanced binary search tree BST

40

/

20 60

/ /

 10 30 40 70