Flatten BST to a Skewed Tree

Flatten BST to a Skewed Tree turns a balanced binary search tree into a single right-leaning chain — like a linked list that only ever goes right. The trick is one of the most reusable ideas with trees: an in-order traversal visits a BST in sorted order, so if we relink nodes as we visit them, the chain comes out sorted for free.

The slow way first

The naive idea: do an in-order traversal, collect every value into a list, then build a brand-new right-leaning tree from that sorted list. That works and is O(n) time, but it uses O(n) extra space for the list and throws away the original nodes.

The question to ask: can I relink the existing nodes during the traversal itself, so I never need the list? Yes — if I remember the previous node I visited, I can attach the current node to it the moment I reach it.

The idea: relink as you traverse

In-order traversal of a BST yields values in sorted order. Keep a single prev pointer for the last node visited. When you reach a node in-order, set prev.right = node, clear node.left, then advance prev = node. A dummy head node lets the very first visited node attach the same way as every other, so there is no special case.

The key insight: because in-order visits values smallest-to-largest, attaching each node to the previous one builds a sorted right-leaning chain in a single pass, reusing the original nodes.

Walk through it

Step through the animation. The traversal dives all the way left to 1, which becomes the chain head. Then 2, 3, the root 4, and the right subtree 5, 6, 7 each get hung off prev as a right child and slide into the descending staircase. The prev marker always points at the tail of the growing chain.

Pseudocode

dummy = new node                # a placeholder head
prev = dummy
inorder(node):
    if node is None: return
    inorder(node.left)
    prev.right = node           # attach current node to the chain
    node.left = None            # no left children in the result
    prev = node                 # current node becomes the new tail
    inorder(node.right)
inorder(root)
return dummy.right              # real head is dummy's right child

The Python solution

def flatten_bst(root):
    dummy = TreeNode()
    prev = dummy
 
    def inorder(node):
        nonlocal prev
        if node is None:
            return
        inorder(node.left)
        prev.right = node
        node.left = None
        prev = node
        inorder(node.right)
 
    inorder(root)
    return dummy.right

• dummy is a throwaway node so the first real node attaches with the same prev.right = node line — no special first-node case.
• prev always holds the last node we appended; it starts at dummy.
• inorder recurses left, processes the node, then recurses right — the classic in-order order.
• Line 10 hangs the current node off the tail of the chain; line 11 clears its left link so the result is purely right-leaning; line 12 advances the tail.
• The final answer is dummy.right, the first node visited in-order (the smallest value).

Complexity

Both approaches are O(n) time, but relinking in place needs only the O(h) recursion stack (height of the tree) instead of an O(n) list. That trade — carry a prev pointer through an in-order walk and rewire links as you go — is the same move behind converting a BST to a sorted doubly linked list.

When this pattern shows up

Practice