Post-Order Traversal — Left, Right, Root

Post-Order Traversal (LRN)

Post-order traversal visits nodes in the order: Left subtree, Right subtree, Node. The root is always the last element in the output, making post-order the natural order for operations that must process children before their parent.

Recursive Implementation

POSTORDER(node):
  if node is NULL: return
  POSTORDER(node.left)
  POSTORDER(node.right)
  visit(node)          // process root last

Example

        4
       / \
      2   6
     / \ / \
    1  3 5  7

Post-order result: [1, 3, 2, 5, 7, 6, 4]

Leaves are visited first (1, 3, 5, 7), then internal nodes bottom-up, and the root (4) is last.

Why Post-Order for Deletion?

When deleting an entire tree, you must free children before their parent to avoid dangling references. Post-order traversal naturally visits children first:

DELETE_TREE(node):
  if node is NULL: return
  DELETE_TREE(node.left)   // free left subtree first
  DELETE_TREE(node.right)  // then right subtree
  free(node)               // finally free the node itself

Expression Tree Evaluation

For an expression tree where internal nodes are operators and leaves are operands, post-order traversal produces postfix (Reverse Polish) notation:

        *
       / \
      +   3
     / \
    1   2

Post-order: [1, 2, +, 3, *] → (1 + 2) * 3 = 9

Two-Stack Iterative Implementation

Post-order is the trickiest traversal to implement iteratively. A common approach uses two stacks: push to stack1 in modified pre-order (root, right, left), then pop all elements from stack1 into stack2 to reverse the order.

Time and Space Complexity

• Time: O(n) — visits every node once
• Space: O(h) — recursion depth equals tree height