This post is completed by 2 users

  • 1
 Add to List
Medium

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:

DLL TO BST 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
Doubly Linked List To BST
Doubly Linked List TO BST - Output
 

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: