Course contentsShow
← Computer Science
Lesson 476 of 2,87211. Binary TreesFree lesson

Implementing Postorder Recursively

Writing recursive postorder traversal: recurse left, recurse right, process current node, for bottom-up processing.

Implementing Postorder Recursively

What you'll learn: How to write the recursive code for postorder traversal to process a binary tree from bottom to top.


The Core Idea

Postorder traversal visits nodes in the order: left subtree, right subtree, then current node. The recursive implementation follows this pattern directly: make two recursive calls (left, then right), and only after both complete do you process the current node's data.

Think of it like cleaning up a workspace from the ground up—you finish all the detail work in the corners first, then handle the main area last.

The Recursive Pattern

The postorder function checks if the current node is null (base case). If not, it:

  1. Recursively traverses the left subtree
  2. Recursively traverses the right subtree
  3. Processes the current node (print, store, compute, etc.)

This is the mirror opposite of preorder, where you processed the node first. Here, processing happens last, after all descendants have been handled.

Example Structure

function postorder(node):
    if node is null:
        return
    
    postorder(node.left)   // recurse left
    postorder(node.right)  // recurse right
    process(node.data)     // process current

For a tree with root 5, left child 3, and right child 8, this visits: 3, 8, 5 (children before parent).

Why It Matters

Postorder is essential for bottom-up operations: deleting trees (free children before parent), evaluating expression trees (compute operands before operator), and calculating subtree properties (get child sizes before parent size).

Key Takeaway: Postorder recursion processes children completely before touching the parent, enabling bottom-up computations by placing the process step after both recursive calls.