Convert BST to Sorted Doubly Linked List

Table of Contents +

This question hides a neat fact about binary search trees. Read one the right way and the values come out already sorted. So turning it into a sorted list is mostly about reusing pointers you already have. The real test is whether you can rewire the left and right pointers in place without losing your way.

🎯 The Problem

You get a binary search tree and must turn it into a sorted circular doubly linked list.

The rules:

A binary search tree, or BST, has every left child smaller than its parent and every right child larger.
A doubly linked list is a chain where each node points to the next one and back to the previous one.
You reuse the same nodes. The left pointer becomes “previous” and the right pointer becomes “next”.
The list must be circular, so the last node links back to the first.

Input (BST):
        4
       / \
      2   5
     / \
    1   3

Output (circular doubly linked list):
    1 <-> 2 <-> 3 <-> 4 <-> 5  (and 5 links back to 1)

Explanation:
  Reading the BST in sorted order gives 1, 2, 3, 4, 5.
  Each node's left points to the previous, right to the next.

Here is the BST. Reading it smallest to largest is the order we want in the list.

🐢 Approach 1: Collect Into an Array Then Link (Brute Force)

The idea in one line: read the BST into a sorted array first, then join the neighbors in a second pass.

The idea:

Reading a BST left, then node, then right gives sorted values. That order is called in-order traversal.
Pour those nodes into an array. The array is now sorted.
Then walk the array and link neighbors.

How it works:

In the second pass, set each node’s right to the next node and its left to the previous one.
Finally link the last node and the first node to make the list circular.

Why it is weak:

You build a whole extra array of size n just to hold the nodes. That is O(n) extra memory.
The work splits into two phases, collect then link, so two passes over the nodes.
We can fold both phases into one.

Here is the collect-and-link code:

def tree_to_doubly_list(root):
    if not root: return None
    nodes = []
    def inorder(node):
        if node:
            inorder(node.left); nodes.append(node); inorder(node.right)
    inorder(root)
    for i, node in enumerate(nodes):
        node.left = nodes[i - 1]
        node.right = nodes[(i + 1) % len(nodes)]
    return nodes[0]

⚡ Approach 2: Link During the In-Order Walk (Best)

The idea in one line: do the in-order walk, but join each node to the one before it as you visit, not after.

The idea:

Keep a pointer prev that holds the last node you visited.
Keep a pointer head that holds the smallest node, the start of the list.

How it works:

When you reach a node, you already visited everything smaller. So prev is the node just before it in sorted order.
Link them. Set prev.right to the current node and current.left to prev. Then move prev forward.
The first node visited is the smallest, and there is no prev yet, so it becomes the head.
At the end, prev sits on the largest node. Link the largest and the head both ways to close the circle.

Why it is fast:

One in-order walk does both the reading and the linking.
No extra array, so the extra memory is just the recursion stack.

This diagram shows prev trailing one step behind as the in-order walk links each pair.

Steps to Solve

If the tree is empty, return nothing.
Keep two pointers, prev and head, both starting empty.
Walk the tree in-order, left subtree, then node, then right subtree.
At each node, if prev is empty, this is the smallest node, so set head to it.
Otherwise link prev.right to the node and the node’s left back to prev.
Move prev to the current node and continue.
After the walk, link prev and head both ways to close the circle. Return head.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

This Python version carries prev and head in a small state object and links nodes as the in-order walk visits them.

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


def bst_to_dll(root):
    if not root:
        return None
    state = {"prev": None, "head": None}   # prev = last visited, head = smallest

    def inorder(node):
        if not node:
            return
        inorder(node.left)                 # visit smaller values first
        if state["prev"] is None:
            state["head"] = node           # first visit is the smallest node
        else:
            state["prev"].right = node     # previous node points forward
            node.left = state["prev"]      # current node points back
        state["prev"] = node               # move prev to current
        inorder(node.right)                # then visit larger values

    inorder(root)
    state["head"].left = state["prev"]     # close the circle both ways
    state["prev"].right = state["head"]
    return state["head"]


root = Node(4)
root.left = Node(2)
root.right = Node(5)
root.left.left = Node(1)
root.left.right = Node(3)

head = bst_to_dll(root)
# print one full loop forward from head
values = []
cur = head
while True:
    values.append(cur.val)
    cur = cur.right
    if cur == head:
        break
print(values)

The output of the above code will be:

[1, 2, 3, 4, 5]

Let us walk the Python version line by line, because the pointer rewiring is the heart of the problem.

The line if not root: return None returns early for an empty tree. No nodes means no list.

The line state = {"prev": None, "head": None} holds two pointers. prev is the last node we linked. head is the smallest node, the front of the list. We keep them in a dictionary so the inner function can change them.

Inside inorder, the line inorder(node.left) recurses left first. In a BST, left holds smaller values. So we always reach the smallest node before anything else. That ordering is why the list comes out sorted.

The branch if state["prev"] is None: state["head"] = node runs only once, on the very first node visited. That node is the smallest, so it becomes the head.

The else branch does the linking. state["prev"].right = node makes the previous node point forward to this one. node.left = state["prev"] makes this node point back to the previous one. Now two neighbors are joined both ways.

The line state["prev"] = node moves prev forward. So the next node visited will link to this one. prev always trails exactly one step behind the walk.

The line inorder(node.right) then visits the larger values, keeping the sorted order.

After the walk, state["head"].left = state["prev"] and state["prev"].right = state["head"] close the loop. At this point prev is the largest node. We link the largest and the smallest both ways. That makes the list circular.

⏱️ Time and Space Complexity

Both ways read every node once in-order, so both are O(n) in time. The array way also builds a list of all n nodes, so it spends O(n) extra memory. The in-place way only keeps two pointers plus the recursion stack. So its extra space is just the stack, which is O(h), where h is the tree height. On a balanced tree that is O(log n).

Approach	Time Complexity	Space Complexity
Collect into array then link	O(n)	O(n)
Link during in-order walk	O(n)	O(h)

Tip

The line to remember is that in-order on a BST gives sorted order for free. Say that first. Then the only work left is joining each node to the one before it.

🧩 Key Takeaways

✅ In-order traversal of a BST visits values in sorted order.
✅ Keep a prev pointer that trails one step behind the walk.
✅ At each node, set prev.right to it and its left back to prev.
✅ The first node visited is the smallest, so make it the head.
✅ After the walk, link the largest node and the head both ways to make the list circular.

Check Your Knowledge

4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Previous Symmetric Tree Next Number of Islands

Convert BST to Sorted Doubly Linked List

Follow Us

Follow Us