See all coding puzzles and patterns here.

Problem Definition

Given a binary search tree (BST), convert it to a doubly-linked list, with each element's previous reference pointing to the next lesser element and its next reference pointing to the next greater element.

Node and Item Classes

Below are the Node and Item classes that will represent nodes in the input BST and the items in the output doubly-linked list. 

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

class Item:
    def __init__(self, value, prev=None, nxt=None):
        self.value = value
        self.prev = prev
        self.nxt = nxt

Example

For this binary tree:

       4
     /   \
    2     6
   / \   / \
  1   3 5   8
 /         / \
0         7   9

The resulting doubly-linked list should be:

                | |->| |->| |->| |->| |->| |->| |->| |->| |->| |
return pointer->|0|  |1|  |2|  |3|  |4|  |5|  |6|  |7|  |8|  |9|
                | |<-| |<-| |<-| |<-| |<-| |<-| |<-| |<-| |<-| |

Solution

This is a graph traversal problem that can best be solved with a depth-first traversal. 

def helper(root: Node) -> tuple[Item, Item]:
    """
    Return (least Item, greatest Item)
    """
    item = Item(root.value)
    if root.left is None:
        least = item
    else:
        least, prev = helper(root.left)
        prev.nxt = item
        item.prev = prev
    if root.right is None:
        greatest = item
    else:
        nxt, greatest = helper(root.right)
        nxt.prev = item
        item.nxt = nxt
    return least, greatest

def convert_bst_to_dl_list(root: Node) -> Item:
    return helper(root)[0]

Complexity

Let $n = $ the number of nodes in the BST.

Since we are visiting every node only once, the runtime complexity should be $\Theta(n)$.

At some points, we might have $2 \cdot log(n)$ stack frames in our program stack; so the auxiliary space complexity should be $O(log(n))$.