AlgoMaster Logo

Binary Tree Postorder Traversal

easyFrequency7 min readUpdated June 23, 2026

Understanding the Problem

We need to traverse a binary tree in postorder, which means: visit the left subtree first, then the right subtree, then the current node. This is the opposite of preorder (root, left, right) and different from inorder (left, root, right).

The recursive solution follows directly from this definition. The interesting part is the iterative version. Postorder is the hardest of the three traversals to do without recursion, because the root must be emitted last but is the first node reached while descending. An iterative solution has to return to each node after both of its subtrees are finished.

One relationship makes this manageable: postorder (left, right, root) is the reverse of a root-right-left traversal, which reduces iterative postorder to a small variation on iterative preorder.

Key Constraints:

  • Number of nodes in range [0, 100] → Small input, so performance is not the concern. The problem is about implementing the traversal correctly, especially without recursion.
  • The tree can be empty (0 nodes), so the code must handle a null root.

Approach 1: Recursive DFS

Intuition

Postorder traversal is defined recursively: visit the left subtree, visit the right subtree, then visit the root. The code follows the definition: recurse left, recurse right, append the current node's value.

The recursion solves the "come back to the root after both subtrees" problem through the call stack. When the left recursive call returns, the right one starts. When the right one returns, the current node is appended. The call stack does all the bookkeeping.

Algorithm

  1. Create a result list.
  2. Define a recursive helper postorder(node):
    • If node is null, return. This also covers an empty tree.
    • Recurse on the left child.
    • Recurse on the right child.
    • Add node.val to the result.
  3. Call postorder(root) and return the result.

Example Walkthrough

1Start postorder(1): go left first
1current23
1/6

Code

The recursive solution is optimal in time, but it relies on the call stack, and a deep enough tree overflows it. The next two approaches manage an explicit stack instead.

Approach 2: Iterative with Reverse Modified Preorder

Intuition

A preorder-style traversal that visits the root, then the right child, then the left child produces the sequence root, right, left. Reversed, that sequence is left, right, root, which is postorder.

This sidesteps the hard question of deciding when a node's subtrees are finished. A root-right-left traversal is as easy to write with a stack as ordinary preorder, and one reversal at the end converts its output to postorder.

Algorithm

  1. If the root is null, return an empty list.
  2. Create a stack and push the root onto it.
  3. Create a result list.
  4. While the stack is not empty:
    • Pop a node from the stack.
    • Add its value to the result.
    • If the node has a left child, push it onto the stack.
    • If the node has a right child, push it onto the stack.
  5. Reverse the result list and return it.

We push left before right. Since a stack is LIFO, the right child gets popped first. This gives us root-right-left traversal order. Reversing produces left-right-root, which is postorder.

Example Walkthrough

1Push root (1) onto stack
1push23
1/5

Code

The reversal produces the correct list, but the nodes are processed in root-right-left order and only rearranged at the end. If something had to happen at each node in postorder position (freeing the node, computing a subtree aggregate), this ordering would be wrong. The final approach visits each node in true postorder position with a single stack and no reversal.

Approach 3: Iterative with Single Stack (True Postorder)

Intuition

This approach reproduces what the recursion does, without the reversal. At each node, the left subtree must be processed, then the right subtree, then the node itself, but a stack-based descent reaches the node before either subtree. The node has to stay on the stack until both subtrees are done.

A previous pointer that tracks the last node added to the result resolves this. When we peek at the top of the stack, its left subtree is already finished (we only peek after descending as far left as possible). If its right child is null or equals previous, the right subtree is also finished, so the node can be popped and processed. Otherwise the traversal moves into the right child.

Algorithm

  1. Create a result list and a stack. Set current = root and previous = null.
  2. While current is not null or the stack is not empty:
    • While current is not null, push current onto the stack and move to current.left.
    • Peek at the top of the stack.
    • If the top node's right child is null or equals previous (right subtree is done):
      • Pop the node, add its value to the result, set previous = node, and set current = null.
    • Otherwise, move to the right child: current = top.right.
  3. Return the result.

An empty tree never enters the loop, so no separate null check is needed.

Example Walkthrough

1Push left chain: push 3, push 1. Stack: [3, 1]
3stack1peek2
1/5

Code