DSA Traversals

Post-order Traversal

A build system must compile leaf packages before the library that imports them, and free child resources before their owning parent. Acting on a parent early leaves dangling references or incomplete aggregates.

is that contract: Left → Right → Root. Descendants always finish before the node that depends on them.

Algorithm journey

Need children first?

Aggregate, evaluate, validate, or clean up bottom-up.

Finish left, finish right, then process the node.

Distinguish first visit from post-child emit.

Push right then left

LIFO makes the left subtree run first.

What actually happens

Naive idea: free or summarize a parent as soon as you see it (pre-order). Wrong for cleanup and for any value that needs both child results.

Better idea: finish both subtrees, then emit. Recursive code places the visit after both calls; iterative code needs an explicit continuation.

The improved design still fails on graphs with shared nodes (visit states required), on deep recursion, and if destructive cleanup drops child pointers before scheduling them.

Invariant / guarantee

For every node x, every descendant of x appears before x in the output. When an expanded frame for x reaches the top of an iterative stack, both child subtrees are already complete.

How to choose post-order

1. Does the parent need finished children? Height, size, expression eval, directory totals, safe delete: yes.

2. Creating top-down? Pre-order. Sorted BST keys? In-order.

3. Iterative? Budget an expanded bit or last-visited pointer; a bare node stack is not enough.

Quantitative check

Θ(n) time; Θ(h) stack. On a skewed tree of n = 10⁵, recursive post-order can overflow before emitting the root (the root is last). Prefer an explicit stack when depth is input-controlled.

Think in completed subproblems

Example

For root A with children B and C, where B owns D and E and C owns F and G, post-order isD, E, B, F, G, C, A.

Contract

A call on node x completely processes x's left subtree, then its right subtree, and only then processes x. A null call does nothing. When the call returns, the whole subtree rooted at x is complete.

Build and traverse a tree

Build a tree, start post-order, and notice that no parent appears while either child subtree remains unfinished.

Build a tree and click Play!

Result:

Empty Tree

Why iterative post-order needs a continuation

A plain node stack cannot distinguish “first time seen” from “children already finished.” Switch execution models below to see an explicit expanded marker replace the recursive return address.

Frames, continuations, and output

Follow the same post-order contract implemented by the language call stack or by an explicit stack.

Step 1 of 43

Ready to call walk(A)

The output and the language call stack both start empty.

Stack (top first)

empty

Output prefix

Nothing visited yet

Invariant: A node is emitted only after every node in both of its subtrees.

Timeline

Recursive implementation

The placement of the visit after both calls is the entire semantic difference from the other depth-first traversals.

Python

python

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


def postorder(root):
    result = []

    def walk(node):
        if node is None:
            return
        walk(node.left)
        walk(node.right)
        result.append(node.value)

    walk(root)
    return result


root = Node(1, Node(2, Node(4), Node(5)), Node(3))
print(postorder(root))  # [4, 5, 2, 3, 1]

Java

java

import java.util.ArrayList;
import java.util.List;

public class PostorderRecursive {
    static class Node {
        int value;
        Node left, right;

        Node(int value) { this.value = value; }
        Node(int value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    static List<Integer> postorder(Node root) {
        List<Integer> result = new ArrayList<>();
        walk(root, result);
        return result;
    }

    static void walk(Node node, List<Integer> result) {
        if (node == null) return;
        walk(node.left, result);
        walk(node.right, result);
        result.add(node.value);
    }

    public static void main(String[] args) {
        Node root = new Node(1,
            new Node(2, new Node(4), new Node(5)),
            new Node(3));
        System.out.println(postorder(root)); // [4, 5, 2, 3, 1]
    }
}

One-stack iterative implementation

Each frame carries an expanded bit. An unexpanded frame schedules a future emit plus its children; an expanded frame emits immediately. Push right before left because the stack is LIFO.

Python

python

def postorder_iterative(root):
    if root is None:
        return []

    result = []
    stack = [(root, False)]

    while stack:
        node, expanded = stack.pop()

        if expanded:
            result.append(node.value)
            continue

        # This continuation must run after both children.
        stack.append((node, True))
        if node.right is not None:
            stack.append((node.right, False))
        if node.left is not None:
            stack.append((node.left, False))

    return result

Java

java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

final class PostorderIterative {
    static final class Node {
        final int value;
        Node left, right;

        Node(int value) {
            this.value = value;
        }
    }

    static final class Frame {
        final Node node;
        final boolean expanded;

        Frame(Node node, boolean expanded) {
            this.node = node;
            this.expanded = expanded;
        }
    }

    static List<Integer> traverse(Node root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        Deque<Frame> stack = new ArrayDeque<>();
        stack.push(new Frame(root, false));

        while (!stack.isEmpty()) {
            Frame frame = stack.pop();
            Node node = frame.node;

            if (frame.expanded) {
                result.add(node.value);
                continue;
            }

            stack.push(new Frame(node, true));
            if (node.right != null) {
                stack.push(new Frame(node.right, false));
            }
            if (node.left != null) {
                stack.push(new Frame(node.left, false));
            }
        }
        return result;
    }
}

The key invariant

Whenever an expanded frame for x reaches the top, every frame created for x's left and right subtrees has already been popped and completed. Therefore emitting x cannot precede a descendant. Each node creates exactly one expanded frame, so each node is also emitted exactly once.

Why push right before left?

LIFO exposes the last push first. Pushing right and then left makes the entire left subtree execute first.

Alternative designs

Two stacks are easier to derive but use another container; tracking the last visited node avoids the flag but has subtler state.

Complexity and recursion depth

Post-order traversal time and space complexity
Measure	Bound	Explanation
Time	Θ(n)	Each node is entered and emitted once.
Recursive stack	Θ(h)	One suspended call per level.
Explicit stack	Θ(h)	Frames and saved continuations stay near the active root-to-leaf frontier.
Stored output	Θ(n)	Omit this cost if values are streamed to a consumer.

A balanced tree has h = Θ(log n); a skewed tree has h = Θ(n). Deep recursive post-order can overflow the call stack before reaching the first output, so prefer an explicit stack for untrusted depth.

Bottom-up applications

Subtree dynamic programming

Compute height, size, balance, or aggregate values from completed child results.

Dependency cleanup

Release or detach descendants before releasing their owning parent.

Expression evaluation

Evaluate operand subtrees before applying the parent operator.

Directory totals

Sum child directory sizes before reporting the enclosing directory.

Choose by the parent's timing

Comparison of pre-order, in-order, and post-order parent timing
Order	Parent timing	Typical intent
Pre-order	Before both children	Create, serialize, announce, or propagate top-down state.
In-order	Between children	Observe binary structure or enumerate a BST in order.
Post-order	After both children	Aggregate, evaluate, validate bottom-up, or clean up.

Edge cases and failure modes

Empty tree: return an empty sequence without constructing a frame around null.
Single node: it is simultaneously a leaf and the final output.
Shared or cyclic graph: ordinary tree traversal assumes one parent path; use visit states for graphs.
Destructive cleanup: save any child references needed for scheduling before removing links.

Exercises

For the A/B/C/D/E/F/G tree used above, write post-order. Which nodes must appear before C? Before A?
Explain why a one-stack iterative post-order needs an expanded bit (or equivalent). What goes wrong if you emit on first pop like pre-order?
You compute subtree sizes with post-order DP. What breaks if a child pointer is shared by two parents (a DAG, not a tree)?

Primary sources

Cormen et al., Introduction to Algorithms (CLRS): postorder / topological intuition on trees and DAGs.
Knuth, TAOCP Vol. 1: postorder and stack-based simulations.
Aho, Sethi, Ullman: expression trees and postfix evaluation as post-order.