DFS Traversals

Visiting every node — but in what order?

"Traverse the tree" means visit every node exactly once. The previous lesson showed the recursive skeleton that does this in O(n). But a tree branches, so unlike an array there is no single obvious order — at every node you have three things to do (process this node, recurse left, recurse right) and the order you interleave them in is a genuine choice with genuine consequences. Depth-first search (DFS) commits to going as deep as possible down one branch before backing up. The three classical DFS orders differ in exactly one thing: when the current node gets processed relative to its two subtrees.

The three orders, by the single rule that defines each

Let "visit" mean do the work at this node (print it, collect its value, whatever). In all three, you still recurse left then right; only the placement of the visit moves:

• Preorder: visit node, then recurse left, then recurse right. The node is handled before its subtrees — "root first."
• Inorder: recurse left, then visit node, then recurse right. The node is handled between its two subtrees — "root in the middle."
• Postorder: recurse left, then recurse right, then visit node. The node is handled after both subtrees — "root last."

The names are literal: pre/in/post describe where the node's own visit sits relative to its children's. On this tree —

• Preorder: 1, 2, 4, 5, 3 (node, then its left subtree, then its right)
• Inorder: 4, 2, 5, 1, 3 (left subtree, node, right subtree)
• Postorder: 4, 5, 2, 3, 1 (both subtrees, then node)

Trace preorder by hand once: at 1 we emit 1, then descend left to 2, emit 2, descend left to 4, emit 4 (4 is a leaf, both recursions hit null and return), back at 2 we descend right to 5, emit 5, back to 1, descend right to 3, emit 3. The recursion's back-and-forth is the traversal.

The recursive implementations

Each is the module's skeleton with the visit line moved. Nothing else changes:

def preorder(node: TreeNode | None, out: list[int]) -> None:
    if node is None:
        return
    out.append(node.val)        # visit BEFORE the subtrees
    preorder(node.left, out)
    preorder(node.right, out)

def inorder(node: TreeNode | None, out: list[int]) -> None:
    if node is None:
        return
    inorder(node.left, out)
    out.append(node.val)        # visit BETWEEN the subtrees
    inorder(node.right, out)

def postorder(node: TreeNode | None, out: list[int]) -> None:
    if node is None:
        return
    postorder(node.left, out)
    postorder(node.right, out)
    out.append(node.val)        # visit AFTER the subtrees

All three are O(n) time — each node is reached once and does O(1) work at its visit — and O(h) space for the recursion stack, where h is the height, because the deepest chain of un-returned calls runs from the root to the current node (one frame per level). This is the O(h) stack cost from the previous lesson, now with concrete code behind it.

When each order is the right tool

The orders aren't interchangeable trivia; each matches a class of problem:

• Postorder is the natural fit whenever a node's answer depends on its children's answers — you must finish both subtrees before you can combine. Computing height, diameter, "is this subtree balanced," deleting a tree (free the children before the parent) — all postorder. This is "bottom-up" recursion, the subject of two lessons from now, and it is the most common shape in this module.
• Preorder fits when a node's work depends on information coming from above — passing a running path, a depth, or a prefix down to children. Serializing a tree (next-to-last lesson) emits preorder so the root comes first and reconstruction can start from it. This is "top-down."
• Inorder has one headline use, next.

Why inorder on a BST yields sorted output

Preview of Module 18. A binary search tree maintains one invariant at every node: everything in the left subtree is smaller than the node, and everything in the right subtree is larger. Now apply the inorder rule — left subtree, then node, then right subtree — and ask what it prints:

Inorder emits everything smaller than the node (the entire left subtree, recursively in sorted order by the same argument), then the node itself, then everything larger (the right subtree, sorted). So for every node, its value lands in the output after all smaller values and before all larger ones. That is the definition of sorted order. By induction over the tree, inorder traversal of a BST produces its values in ascending order — in O(n), with no comparison sort needed, because the BST's structure already encodes the order and inorder is exactly the walk that reads it out. Keep this fact; the next module builds heavily on it.

The iterative version: making the call stack explicit

Recursion is doing bookkeeping for you invisibly: every time inorder calls itself, the language pushes a stack frame remembering where to resume — specifically, which node it was working on and that it still owes "visit the node, then recurse right" after the left call returns. An iterative traversal does that same bookkeeping by hand, with an explicit stack. This matters when recursion depth would overflow the call stack (a degenerate tree of height n), and it makes the hidden mechanism visible.

Here is inorder, iteratively:

def inorder_iterative(root: TreeNode | None) -> list[int]:
    out: list[int] = []
    stack: list[TreeNode] = []
    curr = root
    while curr is not None or stack:
        while curr is not None:      # go as far LEFT as possible,
            stack.append(curr)       # remembering each node we pass
            curr = curr.left
        curr = stack.pop()           # backtrack to the deepest un-visited node
        out.append(curr.val)         # visit it (left subtree is now done)
        curr = curr.right            # then turn to its right subtree
    return out

Read the stack as memory the recursion had for free. In the recursive version, when you descend left, the language remembers on your behalf, "once this left call finishes, come back to this node, visit it, then go right." The while curr is not None: push; go left loop is doing precisely that remembering — it stacks up the chain of ancestors you'll need to return to. Popping pulls back the deepest node whose left side is fully explored (that's why we visit it now — inorder's "node after left subtree" rule), and setting curr = curr.right is the deferred "then go right." The explicit stack holds exactly the nodes the call stack would have held as frames: the current root-to-node spine, at most O(h) of them.

Trace it on the 3-node tree with root 2, left child 1, right child 3: curr = 2 is not null, so push it (stack = [2]) and descend left; curr = 1 is not null, push it (stack = [2, 1]) and descend left again; curr is now null, so the inner loop stops. Pop 1 (stack = [2]), visit it — output [1] — and set curr = 1.right = null. The inner loop does nothing this time (curr is already null), so pop 2 (stack = []), visit it — output [1, 2] — and set curr = 2.right = 3. The inner loop pushes 3 (stack = [3]) and descends left into null. Pop 3 (stack = []), visit it — output [1, 2, 3] — and curr = 3.right = null. Both curr and the stack are now empty, so the outer loop ends. Final output [1, 2, 3], sorted order for what happens to be a valid BST — exactly the property the previous section proved in general.

Same output as the recursive version, same O(n) time, same O(h) space — but now the space is a heap-allocated list you control, not the call stack, so a height-n tree can't blow the recursion limit. That is the entire reason to prefer the iterative form when it matters.