BST Preorder to Postorder

BST Preorder to Postorder turns one tree traversal into another without ever building the tree. The trick is that a Binary Search Tree's ordering lets you find the boundary between the left and right subtree by value alone.

The slow way first

The obvious idea: rebuild the actual BST from the preorder list (inserting each value), then run a normal postorder traversal over it. That works, but it allocates a whole tree of node objects and, with naive insertion, can degrade to O(n²) on a skewed input.

The question to ask: do I actually need the tree? The values already encode the structure — so I can recurse on the array directly and emit postorder as I go.

The idea: root first, then partition by value

In a preorder list the first value is always the root. Because it is a BST, every value in the left subtree is smaller than the root and every value in the right subtree is larger. And preorder keeps each subtree contiguous — so the left subtree is a run of values right after the root, ending the moment we hit the first value >= root. That index is the split.

Postorder is left, then right, then root, so once the two recursive calls return their lists we just concatenate them and append the root.

Walk through it

Step through the animation. The top strip is the preorder input; the split pointer scans for the first value at least as big as the root (5). Values 3, 1, 4 are all smaller, so they form the left subtree; 8, 6, 9 form the right. The bottom strip fills with the left subtree's postorder, then the right's, and finally the root 5 lands at the very end.

Pseudocode

function pre_to_post(preorder):
    if preorder is empty: return []
    root = preorder[0]                      # preorder always starts with the root
    split = length(preorder)                # default: no right subtree
    for i from 1 to length(preorder) - 1:
        if preorder[i] >= root:             # first value too big to be on the left
            split = i
            break
    left  = pre_to_post(preorder[1 .. split])   # values smaller than root
    right = pre_to_post(preorder[split .. end])  # values larger than root
    return left + right + [root]            # postorder = left, right, root

The Python solution

def pre_to_post(preorder):
    if not preorder:
        return []
    root = preorder[0]
    split = len(preorder)
    for i in range(1, len(preorder)):
        if preorder[i] >= root:
            split = i
            break
    left = pre_to_post(preorder[1:split])
    right = pre_to_post(preorder[split:])
    return left + right + [root]

• The base case: an empty slice has no postorder, so return [].
• root = preorder[0] — preorder emits the root before anything else, so the first value is always the root.
• split starts at len(preorder), meaning no right subtree; the loop lowers it if it finds a larger value.
• Line 7 is the heart: the first value >= root is where the left subtree ends and the right begins.
• preorder[1:split] is the left subtree (all < root); preorder[split:] is the right subtree (all >= root).
• Line 12 assembles postorder order — left, then right, then root — by concatenation.

Complexity

The recursion replaces an explicit tree with the call stack and slices, so we never allocate node objects. Slicing copies sub-arrays, which is what pushes the worst case to O(n²); passing index bounds instead of slices would bring it down.

When this pattern shows up

Practice