Binary Tree Postorder Traversal

easy tree dfs stack

Problem

Return the postorder (left, right, root) traversal of a binary tree's node values.

Inputroot = [1, null, 2, 3]

Output[3, 2, 1]

Trick: do a modified preorder that emits root-right-left (push left first, then right), then reverse — same node count, simpler bookkeeping than a true postorder stack.

level-order (use "null" for missing)

def postorder_traversal(root):
    if not root: return []
    out, stack = [], [root]
    while stack:
        n = stack.pop()
        out.append(n.val)
        if n.left:  stack.append(n.left)
        if n.right: stack.append(n.right)
    return out[::-1]

function postorderTraversal(root) {
  if (!root) return [];
  const out = [], stack = [root];
  while (stack.length) {
    const n = stack.pop();
    out.push(n.val);
    if (n.left) stack.push(n.left);
    if (n.right) stack.push(n.right);
  }
  return out.reverse();
}

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 n = stack.pop();
            out.addFirst(n.val);
            if (n.left != null) stack.push(n.left);
            if (n.right != null) stack.push(n.right);
        }
        return out;
    }
}

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> out;
    if (!root) return out;
    stack<TreeNode*> st; st.push(root);
    while (!st.empty()) {
        auto* n = st.top(); st.pop();
        out.push_back(n->val);
        if (n->left) st.push(n->left);
        if (n->right) st.push(n->right);
    }
    reverse(out.begin(), out.end());
    return out;
}

Explanation

True postorder is left, right, root, which is awkward to do with a stack because the root must come last. The slick trick here is to do an easy traversal that produces root, right, left and then simply reverse it.

We start with the root on a stack. In each step we pop a node, append its value to out, then push its left child first and right child second. Because a stack pops last-in-first-out, the right child comes out before the left, producing the root-right-left order.

That visiting order is exactly the reverse of left-right-root. So at the very end we return out reversed (in Java we cheat by adding each value to the front of the list with addFirst), which gives the correct postorder.

Example: tree [1, null, 2, 3]. We pop 1 (emit 1, push 2), pop 2 (emit 2, push 3), pop 3 (emit 3). Buffer is [1, 2, 3]; reversed it becomes [3, 2, 1].

Each node is pushed and popped once, so this runs in O(n) time.

Time: O(n) Space: O(h)