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:

1. Get the size of the Doubly Linked list.
2. Take left n/2 nodes and recursively construct the left subtree
3. Make the middle node as root and assign the left subtree( constructed in step 2) to the root's left.
4. Recursively construct the right subtree and link it to the right of the root made in step 3.
5. 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

Related Problems:

- Merge Sort for Linked Lists (In-place Algorithm) Medium
- Calculate Distance Between Nodes in a Binary Tree Hard
- Construct a binary tree from given Inorder and Level Order Traversal Hard
- Construct Binary Search Tree from a given Preorder Traversal using Recursion Hard
- Make a Binary Tree from Given Inorder and Preorder Traversal Hard