Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Convert a Sorted Doubly Linked List to Balanced BST.

Objec­tive: Given a sorted dou­bly linked list, con­vert it into Bal­anced binary search tree

Input: A Dou­bly Linked List

Exam­ple:

DLL TO BST Example

DLL TO BST Example

Approach:

  1. Get the size of the Dou­bly Linked list.
  2. Take left n/2 nodes and recur­sively con­struct left subtree
  3. Make the mid­dle node as root and assign the left sub­tree( con­structed in step 2) to root’s left.
  4. Recur­sively con­struct right sub­tree and link it to the the right of root made in step 3.
  5. See pic­ture below
Doubly Linked List To BST

Dou­bly Linked List To BST

Doubly Linked List TO BST - Output

Dou­bly Linked List TO BST — Output

Com­plete Code:


Out­put :

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

You may also like...