Construct a Height-Balanced BST from a Sorted Doubly Linked List

Given a sorted Doubly Linked List, in-place convert it into a height-balanced Binary Search Tree (BST). The difference between the height of the left and right subtree for every node of a height-balanced BST is never greater than 1.


 

For example,

Height-Balanced BST

 
Simple solution is to traverse the doubly linked list, store every node in an array, and then construct a height-balanced BST from nodes in the array. The idea is make middle node in the sorted array as root node of the BST. Then all nodes before the middle node goes in the left subtree and all nodes after the middle node goes in the right subtree. If we follow this recursively for left and right subtree, we will end up with a height-balanced BST. Below is pictorial representation of the above approach followed by the C++ implementation –

 
Convert Sorted DLL To Balanced BST

 

Download   Run Code

Output:

Doubly Linked List: 8 10 12 15 18 20 25
Preorder traversal of the constructed BST: 15 10 8 12 20 18 25

 
The time complexity of above solution is O(n), but it requires O(n) extra space for storing the BST nodes. The conversion can be done in-place without any auxiliary data structure.

 
The idea is to build the BST in inorder fashion i.e same order as nodes appear in the doubly linked list. We start by counting the number of nodes in the doubly linked list. Then recursively construct the left subtree with first half of nodes in doubly linked list, assign middle node of the doubly linked list to the root node of the BST, and set the constructed left subtree as left child of the root node. To get the middle node in constant time, move head pointer of the doubly linked list to the next node after setting the root node of the BST. Finally, recursively construct the right subtree with remaining nodes in the doubly linked list and set it as right child of the root node.

The algorithm can be implemented as follows in C++:

 

Download   Run Code

Output:

Doubly Linked List: 8 10 12 15 18 20 25
Preorder traversal of the constructed BST: 15 10 8 12 20 18 25

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
Notify of