Postorder Traversal

JavaView on GFG

Time: O(n)

Space: O(h)

Intuition

Visit left, right, then root. Iterative: two-stack method or reverse pre-order trick.

Algorithm

1Iterative two-stack: stack1 starts with root. Pop to stack2, push left then right child to stack1. Drain stack2.
2Or: modified pre-order (root, right, left), reverse result.

Common Pitfalls

•Two-stack method is intuitive. Reverse-preorder trick is clever but less obvious.

Postorder Traversal.java

Java

// Approach: Recursive or iterative (two-stack) postorder (left-right-root) traversal of binary tree.
// Time: O(n) Space: O(h)
import java.util.*;

class Node {
    int data;
    Node left, right;

    Node(int val) {
        data = val;
        left = right = null;
    }
}

class Solution {
    public ArrayList<Integer> postOrder(Node root) {
        ArrayList<Integer> res = new ArrayList<>();
        traverse(res, root);
        return res;
    }

    public static void traverse(ArrayList<Integer> res, Node root) {
        if (root == null)
            return;

        traverse(res, root.left);
        traverse(res, root.right);
        res.add(root.data);
    }
}

Was this solution helpful?