This post is completed by 2 users
|
Add to List |
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