Post-order traversal

Post-order traversal is a depth-first walk of a Binary tree that processes the current node after both children: traverse left subtree, traverse right subtree, then process current. The acronym LRN (Left-Right-Node) captures it.

postorder(root) → postorder(left), then postorder(right), then root

The defining property: the current node is visited only when both its subtrees have already been fully visited. This makes post-order the right choice whenever the parent’s processing depends on results computed from the children — tree deletion, expression evaluation, recursive metrics like height.

Recursive implementation

void postorderPrint(BinaryTreeNode *cur) {
    if (cur == NULL) return;
    postorderPrint(cur->left);             // left subtree
    postorderPrint(cur->right);            // right subtree
    printf("%d ", cur->data);              // then current
}

The “process the node” line moves to the bottom — last among the three statements.

Worked example

Take the standard sorted binary tree: root F; F’s children are B (left) and G (right); B’s children are A and D; D’s children are C and E; G has right child I, whose left child is H. Post-order visits a node only after both its subtrees are done (the arrows leave each node from its right side):

Image: Sorted binary tree showing post-order traversal, public domain

Post-order output: A C E D B H I G F

Trace:

1. From F, recurse left into B, then into A. A’s children are NULL. Print A.
2. Back at B, recurse right into D, then into C. Print C. Back at D, recurse right into E. Print E. Both of D’s children done. Print D. Both of B’s children done. Print B.
3. Back at F, recurse right into G. G’s left is NULL; recurse right into I, then into H. Print H. Both of I’s children done. Print I. Both of G’s children done. Print G.
4. Back at F. Both subtrees done. Print F.

Final sequence: A C E D B H I G F. The root comes last; every leaf comes before its parent.

Tree deletion

The canonical use case. To free an entire tree, you must free every child before freeing the parent — otherwise you’d lose the pointers needed to reach the children. Post-order is exactly that order:

void freeTree(BinaryTreeNode *cur) {
    if (cur == NULL) return;
    freeTree(cur->left);
    freeTree(cur->right);
    free(cur);
}

If you tried this in pre-order (free the parent first), you’d dereference freed memory while recursing — undefined behaviour.

Postfix expression evaluation

Post-order traversal of an expression tree produces postfix (Reverse Polish) notation: $(a+b)\cdot c$ becomes a b + c *. This is the form a stack-based calculator can evaluate directly:

1. Read each token left to right.
2. If a number, push.
3. If an operator, pop the top two, apply, push the result.

The match between post-order and postfix is exact — both evaluate operands before operators.

Computing recursive metrics

Many tree metrics need child results before the parent’s:

• Height of a node = $1+\max (\text{height of left child},\text{height of right child})$. Compute children first, then current.
• Subtree size = $1+\text{size of left}+\text{size of right}$. Same pattern.
• Sum of all values = current value + sum of left + sum of right. Same.
• Whether a tree is balanced — needs heights of both subtrees before deciding the current node.

int height(BinaryTreeNode *cur) {
    if (cur == NULL) return -1;
    int hL = height(cur->left);
    int hR = height(cur->right);
    return 1 + (hL > hR ? hL : hR);
}

The two recursive calls are post-order in spirit — both children’s heights are computed before the parent combines them.

Iterative implementation

Post-order is the trickiest of the four orders to do iteratively because you must distinguish “first time visiting this node, descend into children” from “second time visiting, now process it.” Two common approaches:

Two-stack version (simpler).

void postorderIterative(BinaryTreeNode *root) {
    if (root == NULL) return;
    Stack s1 = stack_create(), s2 = stack_create();
    stack_push(&s1, root);
    while (!stack_empty(&s1)) {
        BinaryTreeNode *cur = stack_pop(&s1);
        stack_push(&s2, cur);
        if (cur->left)  stack_push(&s1, cur->left);
        if (cur->right) stack_push(&s1, cur->right);
    }
    while (!stack_empty(&s2)) {
        printf("%d ", stack_pop(&s2)->data);
    }
}

Walk in a “modified pre-order” (root, right, left) pushing onto a second stack, then pop everything off the second stack — that reverses the order to (left, right, root), which is post-order.

One-stack version uses a “previously visited” pointer to know whether to descend further or process the current node. Common in interview answers; messier to read.

Complexity

Time $O(n)$. Space $O(h)$ for the recursion stack (or two stacks for the iterative version).

Comparison

Order	Sequence	When to use
Pre-order	Root, Left, Right	Tree copying, prefix output
In-order	Left, Root, Right	BST sorted output
Post-order	Left, Right, Root	Tree deletion, postfix output, recursive metrics
Level-order	By depth, left-to-right	Shortest paths, layer processing

For the hub note, see Binary tree traversal.