Postorder Traversal of a tree both using recursion and Iteration

The problem, simply

You get a binary tree. Write down every value in this order: everything in the left side, then everything in the right side, and the node itself last. Do the same inside each side. This order is called postorder.

You must do it two ways: with a function that calls itself, and with a loop and your own stack.

A story to remember it

Picture it

Examples

Way 1: the simple way

Write a helper that reads the left side, then the right side, and then writes the node.

1. If the node is empty, return.
2. Read the left side.
3. Read the right side.
4. Write the node's value.

import java.util.*;

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> out = new ArrayList<>();
        read(root, out);
        return out;
    }

    private void read(TreeNode node, List<Integer> out) {
        if (node == null) return;
        read(node.left, out);     // left family
        read(node.right, out);    // right family
        out.add(node.val);        // me last
    }
}

How long it takes: each node once, O(n). Extra room: the call stack, O(h).

Way 2: the clever way

One stack plus one extra finger called last, which points at the node you wrote most recently. It answers the cleaning question: is my right side finished?

1. Slide down the left edge from curr, pushing every node.
2. Peek at the top node (do not pop yet).
3. If it has a right child and that child is not last, the right side is not done. Move curr to the right child and go back to step 1.
4. Otherwise both sides are done. Pop it, write it, and set last to it.
5. Stop when curr is empty and the stack is empty.

import java.util.*;

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> out = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode curr = root, last = null;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {              // slide down the left edge
                stack.push(curr);
                curr = curr.left;
            }
            TreeNode top = stack.peek();
            if (top.right != null && top.right != last) {
                curr = top.right;               // right side not finished yet
            } else {
                stack.pop();                    // both sides finished
                out.add(top.val);
                last = top;                     // remember who finished last
            }
        }
        return out;
    }
}

How long it takes: each node is pushed once and popped once, O(n). Extra room: the stack holds the current way down, O(h).

Way 3: two stacks, or a reversed trick

There is an easier iterative version. Do a preorder walk but push left before right, so you read "me, right, left". Reverse that list and you get "left, right, me", which is postorder. You can collect into a second stack and pop it, or add each value to the front of a linked list.

import java.util.*;

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> out = new LinkedList<>();
        if (root == null) return out;
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            out.addFirst(node.val);                      // front, so the list ends up reversed
            if (node.left != null) stack.push(node.left);
            if (node.right != null) stack.push(node.right);
        }
        return out;
    }
}

This is also O(n) time with an O(h) stack. But it is not a true postorder walk. It meets every parent before its children and only fixes the order by reversing at the end, so you cannot do work on a node at the moment its children finish, which is what problems like "delete the tree" need. Way 2 can.

Watch out for

• Popping before checking. Use peek first; only pop once both sides are done.
• Writing last = top must happen right when you pop, not later.
• In Way 3, pushing right before left gives the wrong order after the reverse.

What interviewers ask next

• Why does postorder matter? It is the natural order for "children first" jobs: deleting a tree, freeing memory, computing heights or subtree sums, and evaluating an expression tree.
• Delete every node of a tree safely. Postorder, so a parent is removed only after its children.
• Evaluate (3 + 4) * 2 stored as a tree. Postorder gives 3 4 + 2 *, which a stack can compute.
• Can you do it in O(1) extra room? Yes, with a Morris style walk that writes each left family's right edge backwards, but it is rarely asked to code.

Remember this

Grown-up words: the pile of open doors is a stack, peeking is peek(), the finger last is the previously visited node, and the "children first" order is postorder depth first search.