The DFS Skeleton#
Every depth-first traversal of a binary tree (pre-order, in-order, post-order) is the same three-line shape:
The only thing that distinguishes the three orderings is where you slot in the "visit this node" step:
- Pre-order: visit before both recursive calls.
- In-order: visit between the two recursive calls.
- Post-order: visit after both recursive calls.
That's it. Three orderings, one skeleton. Don't memorise them as three different algorithms. Memorise the skeleton and remember the visit position. The rest follows.
Three Orderings, One Tree#
Here's a 7-node tree. The output column on the right shows what each ordering produces when applied to it.
Pay attention to where 1 (the root) appears in each output: first in pre-order, middle in in-order, last in post-order. That single observation captures the whole distinction.
When to Use Which?#
| Ordering | Use it when… | Classic example |
|---|---|---|
| Pre-order | You need to process a node before its children, which is typical for cloning, copying, or serialising a tree top-down. | Tree clone, serialise to a string |
| In-order | You're walking a BST and want values in sorted order. | Validate a BST, print BST contents sorted |
| Post-order | You need a node's children's results before computing its own value. | Delete a tree, compute heights, sum subtrees |
The rule of thumb: if the parent's work depends on the children, use post-order. If the children's work depends on something the parent computes, use pre-order. If you're reading a sorted BST, use in-order.
The Code#
Each variant is the skeleton with a single visit line moved to a different position. Watch where result.append(node.val) sits.
Three functions, one line of code different between each. That's the whole family.
The Post-Order Pattern#
Post-order deserves its own spotlight because it's the workhorse of tree algorithms. Whenever a problem says "compute something at every node using information from its subtrees", it's a post-order problem.
The reason: when post-order visits a node, both recursive calls have already returned, so the left and right subtree results are sitting in your hands, ready to combine.
The cleanest example is computing the maximum depth of a tree:
Notice the structure: recurse left, recurse right, then do the work using both returned values. That's post-order in its purest form. We're not "visiting" by printing, but we are computing.
The same pattern solves a surprising number of problems:
- Lowest Common Ancestor: each node combines what each subtree found.
- Path Sum: children report partial sums upward.
- Diameter of Binary Tree: each node knows the deepest left and deepest right path.
- Balanced Binary Tree check: each node returns its height and whether its subtree is balanced.
Internalise post-order's "compute up from the leaves" rhythm and a huge swath of tree problems collapses into one technique.
Try It#
Let's take the example of this visualization: a five-node tree, with 0 at the root, 1 and 2 below it, 3 under 1 on the left and 4 under 2 on the right. It runs the in-order walk, so the pointer descends to 3 before recording anything and the OUTPUT rail fills in 3, 1, 0, 2, 4.
As you step through it, keep the skeleton in mind. The descent you are watching is the same descent all three orderings make. Move the visit line and the identical walk would emit 0, 1, 3, 2, 4 (pre-order) or 3, 1, 4, 2, 0 (post-order). Only the moment of recording changes.
Complexity#
- Time: O(N). Every node is visited exactly once. Constant work per node, N nodes, done.
- Space: O(H). The recursion stack is as deep as the path currently being explored, which is at most the tree's height H.
That space bound is worth pausing on:
- For a balanced tree, H = O(log N), so space is roughly O(log N).
- For a completely skewed tree (basically a linked list), H = N, so space is O(N).
This is why building balanced trees matters in practice: it keeps recursion depth (and therefore stack usage) logarithmic, which prevents stack overflows on large inputs.