Problem:

In-place conversion of Sorted DLL to Balanced BST

Given a Doubly Linked List which has data members sorted in ascending order.

Construct a Balanced Binary Search Tree which has same data members as the given Doubly Linked List. The tree must be constructed in-place (No new node should be allocated for tree conversion)

Solution:

– Get middle node

– Process first half part recursively for left sub-tree

– Process right half part recursively for right sub-tree

– Technically its creating node from root to leaves

Latest Source Code:

Github: SortedDLLToBalancedBST.java

**Output:**

Print DLL Forward: 1 2 3 4 5 6 7 Print DLL Reverse: 7 6 5 4 3 2 1 Binary Search Tree : 4 / \ / \ 2 6 / \ / \ 1 3 5 7