Convert a given binary search tree into a doubly linked list such that list is sorted in increasing order | CODING INTERVIEW ARCHIVES

Convert a given binary search tree into a doubly linked list such that list is sorted in increasing order | CODING INTERVIEW ARCHIVES

We are given a binary search tree and we have to convert it into a DLL.
Here, we are proposing a recursive approach and are using circular DLL.

Algorithm:

• Convert the left subtree recursively into DLL left_list.
• Convert the right subtree recursively into DLL right_list.
• Make the root's left and right point to itself thus making it a circular DLL of one node.
• Merge root into left_list.
• Merge right_list into left_list.
• Return left_list.

Code for the same approach can be given as:

Read full article from Convert a given binary search tree into a doubly linked list such that list is sorted in increasing order | CODING INTERVIEW ARCHIVES