66. Convert a Sorted Doubly Linked List to Balanced BST

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

Example:

Approach:

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

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