How would you convert a binary search tree to a doubly-linked list?

Converting a binary search tree (BST) into a doubly-linked list involves an in-order traversal of the BST and properly adjusting the right and left pointers of each node so that they follow the doubly-linked list properties.

Let’s define the process with a recursive function.

def flatten(root):
    if root is None:
        return None
       
    # Initially, both lists are empty
    head, tail = None, None
   
    # Recursively convert the left sub-tree
    if root.left is not None:
        head, tail = flatten(root.left)
       
        # Make right pointer of tail node point to root
        tail.right = root
        # Make left pointer of root point to tail
        root.left = tail
       
    # If left sub-tree is empty, the head is root
    if head is None:
        head = root
   
    # Save the node into tail which is needed when right sub-tree is empty
    temp = root
   
    # Recursively convert the right sub-tree
    if root.right is not None:
        temp, tail = flatten(root.right)
       
        # Make left pointer of first node of result point to root
        temp.left = root
        # Make right pointer of root point to the first node of right sub-tree
        root.right = temp
   
    # If right sub-tree is empty, the tail is root
    if tail is None:
        tail = root
   
    return head, tail

Here, ‘flatten()‘ function takes a root of a BST and returns the head and tail of the doubly linked list. It first checks if the root is ‘None‘ and returns ‘None‘ in this case. Then, it initializes ‘head‘ and ‘tail‘ as ‘None‘.

It recursively flattens the left sub-tree and if the root’s left is not ‘None‘, it makes the right pointer of tail node point to root and makes left pointer of the root point to tail. If the root’s left is ‘None‘, ‘head‘ is root.

It saves the current root into ‘temp‘ which is needed when the right sub-tree is empty.

Similarly, it recursively flattens the right sub-tree and if the root’s right is not ‘None‘, it makes the left pointer of first node of right sub-tree point to root and makes the right pointer of root point to the first node of the right sub-tree. If the root’s right is ‘None‘, ‘tail‘ is root.

Finally, it returns the ‘head‘ and ‘tail‘.

For example, if the BST is:

     10
    /  \
   5   20
  / \  / \
 1  8 15 25

Then, the DLL will be:

1 <-> 5 <-> 8 <-> 10 <-> 15 <-> 20 <-> 25