BST to Sorted Doubly Linked List

BST to Sorted Doubly Linked List is a classic that rewards one observation: an inorder traversal of a binary search tree visits its values in sorted order. Once you see that, the whole problem collapses into "walk in order, and link each node to the one before it."

The slow way first

The obvious approach: do an inorder traversal, collect every value into an array, then build a fresh doubly linked list from that sorted array. That works and is easy to reason about, but it allocates a whole extra array of n nodes — O(n) extra space — when the tree already contains exactly the nodes we need.

The question to ask: while I am visiting nodes in sorted order, why not link them as I go? If I always remember the previous node I visited, I can connect it to the current node on the spot, reusing the tree nodes themselves.

The idea: link to the previous node during inorder

Run a standard inorder walk (left, node, right). Keep one variable, prev, holding the last node we visited. At each node:

• If prev is None, this is the smallest value — record it as the head.
• Otherwise wire them together: prev.right = node and node.left = prev.
• Then set prev = node and continue.

Because inorder hands us nodes in increasing order, every link we make points from a smaller value to the next-larger one — exactly a sorted doubly linked list.

Walk through it

Step through the animation. The BST sits on top; the sorted list grows left to right underneath. Each inorder visit lights up a tree node, reveals it on the list, draws the doubly linked edge back to prev, and then slides prev forward. The first node visited (1) becomes the head; when the walk ends, prev rests on the tail (7).

Pseudocode

head = None        # smallest node, returned at the end
prev = None        # last node visited by the inorder walk
 
inorder(node):
    if node is None: return
    inorder(node.left)              # everything smaller first
    if prev is None:
        head = node                 # first visit = smallest = head
    else:
        prev.right = node           # link previous -> current
        node.left  = prev           # link current  -> previous
    prev = node                     # advance prev
    inorder(node.right)             # everything larger next
 
inorder(root)
return head

The Python solution

def tree_to_dll(root):
    head = None
    prev = None
 
    def inorder(node):
        nonlocal head, prev
        if node is None:
            return
        inorder(node.left)
        if prev is None:
            head = node
        else:
            prev.right = node
            node.left = prev
        prev = node
        inorder(node.right)
 
    inorder(root)
    return head

• head and prev live in the outer function; nonlocal lets the nested inorder reassign them.
• inorder(node.left) recurses into all smaller values before touching the current node — that is what produces sorted order.
• When prev is None, the current node is the very first (smallest) one, so it becomes the head.
• Otherwise the two lines prev.right = node and node.left = prev weld the previous node and the current one into a doubly linked pair.
• prev = node advances the trailing pointer; then we recurse right into the larger values.

Complexity

We visit every node exactly once, so time is O(n). The only extra space is the recursion stack, which is the tree height O(h) — no separate array. That is the win over collecting into a list first.

When this pattern shows up

Practice