Algorithm Magic: Binary Search Tree to Doubly Linked List

Hi friends,

This post gives solution to a famous data structures problem: Converting a Binary Search Tree to Doubly Linked List. I am assuming you are well aware of what there data structures are and their behavior.

Lets jump into algorithm to convert this.

• Since each subtree in a binary tree is a binary tree itself, we can use recursion for achieving this. We start by root node and reach leaf nodes. 
• While traversing, we see if node does not have any left or right child, the node itself is returned. If it has non empty child nodes, then we create doubly linked list with 3 nodes( current node, left child node and parent node). 
• Now here is the magic, the left child is not exactly its direct left child. Since our aim is to convert it into a sorted doubly linked list, we need to get the maximum value node which is less than current node value in left subtree as as left child for current node. Similarly, the node with least value in right subtree as right child of current node. 
• That's it, apply this logic and solve it.

The class used to represent the node in binary tree and doubly linked list*:

*left will indicate previous node in doubly linked list and right will indicate the next node in doubly linked list.

function to insert node in BST:

function to convert BST to DLL:

function to show doubly linked list:

Here is the implementation of this algorithm: Download here.

Hope this helps you learn how to convert BST into DLL.
Cheers!