Tree DFS — Pre/In/Post Orderings

The DFS Skeleton

Every depth-first traversal of a binary tree — pre-order, in-order, post-order — is the same three-line shape:

python

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 — 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.

python

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:

python

Notice the structure: recurse left, recurse right, then do the work using both returned values. That's post-order in its purest form — even though we're not "visiting" by printing, we're computing.

The same pattern unlocks 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

Step through all three DFS orderings on the same tree and watch the visit position shift.

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.

The DFS Skeleton

Every depth-first traversal of a binary tree — pre-order, in-order, post-order — is the same three-line shape:

python

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 — 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 Code

Each variant is the skeleton with a single visit line moved to a different position. Watch where result.append(node.val) sits.

python

Three functions, one line of code different between each. That's the whole family.

The Post-Order Pattern

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:

python

The same pattern unlocks 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

Step through all three DFS orderings on the same tree and watch the visit position shift.

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.