Binary Tree Postorder Traversal

Description

145. Binary Tree Postorder Traversal

Given the root of a binary tree, return the postorder traversal of its nodes’ values.

Example 1:
Input: root = [1,null,2,3]
Output: [3,2,1]
Explanation:

Example 2:
Input: root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output: [4,6,7,5,2,9,8,3,1]
Explanation:

Example 3:
Input: root = []
Output: []

Example 4:
Input: root = [1]
Output: [1]

Constraints:

• The number of nodes in the tree is in the range $[0,100]$.
• $-100\le \text{Node.val}\le 100$

---

Approach 1: Recursive Traversal ($O(N)$ Time, $O(N)$ Space)

Intuition

Traverse the binary tree recursively following the postorder sequence: Left subtree $\to$ Right subtree $\to$ Root node. Recursively visit the left child, then the right child, and append the current node’s value.

import java.util.ArrayList;
import java.util.List;
 
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        postorder(root, result);
        return result;
    }
 
    private void postorder(TreeNode node, List<Integer> result) {
        if (node == null) return;
        postorder(node.left, result);
        postorder(node.right, result);
        result.add(node.val);
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Every node in the binary tree is visited once.
• Space Complexity: $O(N)$ worst-case call stack depth for a skewed tree ($O(\log N)$ for a balanced tree).

---

Approach 2: Iterative Stack (Unified Template — $O(N)$ Time, $O(N)$ Space)

Intuition

This uses the exact same unified template as iterative Preorder and Inorder (curr pointer + nested while loops with ArrayDeque).

Postorder ($\text{Left}\to \text{Right}\to \text{Root}$) is the exact reverse of a mirrored Preorder ($\text{Root}\to \text{Right}\to \text{Left}$). By traversing Right before Left and prepending values (addFirst), we maintain the exact same structural template as Preorder while generating the Postorder sequence.

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
 
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> result = new LinkedList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode curr = root;
 
        while (curr != null || !stack.isEmpty()) {
            // Explore right branch first and prepend values on the way down
            while (curr != null) {
                result.addFirst(curr.val); // Prepend: Reverses Root -> Right -> Left into Left -> Right -> Root
                stack.push(curr);
                curr = curr.right;         // Move RIGHT instead of Left
            }
 
            // Backtrack and step into the left subtree
            curr = stack.pop();
            curr = curr.left;              // Move LEFT after popping
        }
 
        return result;
    }
}
 

1. Why LinkedList instead of ArrayList here?

Because we are inserting elements at the very front (index 0) to reverse the traversal order on the fly:

• LinkedList.addFirst(val) takes $O(1)$ constant time (just updates pointers).
• ArrayList.add(0, val) takes $O(N)$ linear time (must shift all existing elements to the right every time).

Using ArrayList with add(0, val) would degrade the overall time complexity from $O(N)$ to $O(N^2)$.

2. Difference Between ArrayList and LinkedList

Feature	ArrayList	LinkedList
Underlying Data Structure	Resizable Array	Doubly Linked Nodes
Insert/Delete at Ends	$O(N)$ at front, $O(1)$ at end	$O(1)$ at both front and end
Random Access (get(i))	$O(1)$	$O(N)$
Memory Overhead	Lower (contiguous block)	Higher (stores pointers for each node)

---

3. addFirst() vs. Regular add()

• add(val): Appends val to the end of the list.
  • Example: [1, 2] $\to$ add(3) $\to$ [1, 2, 3]
• addFirst(val): Inserts val at the front (index 0) of the list.
  • Example: [1, 2] $\to$ addFirst(3) $\to$ [3, 1, 2]

Complexity

• Time Complexity: $O(N)$ — Each node is pushed, popped, and prepended to the linked list in $O(1)$ time.
• Space Complexity: $O(N)$ — Auxiliary space required for the explicit stack.

---

Approach 3: Morris Postorder Traversal (Unified Mirror Template — $O(N)$ Time, $O(1)$ Space)

Intuition

Mirror the standard Morris Preorder Traversal by creating temporary threads on the right side:

1. Find the in-order successor (leftmost node in the right subtree).
2. Create/destroy threads on succ.left instead of pred.right.
3. Prepend curr.val to the result list when creating a new thread (succ.left == null) or when a node has no right child.

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
 
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> result = new LinkedList<>();
        TreeNode curr = root;
 
        while (curr != null) {
            if (curr.right == null) {
                result.addFirst(curr.val); // Prepend current node
                curr = curr.left;
            } else {
                // Find in-order successor (leftmost node in right subtree)
                TreeNode succ = curr.right;
                while (succ.left != null && succ.left != curr) {
                    succ = succ.left;
                }
 
                if (succ.left == null) {
                    result.addFirst(curr.val); // Visit root BEFORE creating thread and moving right
                    succ.left = curr;          // Temporary thread back to curr
                    curr = curr.right;
                } else {
                    succ.left = null;          // Restore original tree structure
                    curr = curr.left;
                }
            }
        }
 
        return result;
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Each edge is traversed at most twice.
• Space Complexity: $O(1)$ auxiliary space — Pointers are modified temporarily without stack frames.

---

Breakdown: What Changed Across Traversals & How It Works

Comparison of the Unified Iterative Template

Traversal	Target Order	Traversal Order	Result Operation	Loop Movements
Preorder	$\text{Root}\to \text{Left}\to \text{Right}$	$\text{Root}\to \text{Left}\to \text{Right}$	Append (add) on way down	Go .left in inner loop, .right after pop
Inorder	$\text{Left}\to \text{Root}\to \text{Right}$	$\text{Left}\to \text{Root}\to \text{Right}$	Append (add) after pop	Go .left in inner loop, .right after pop
Postorder	$\text{Left}\to \text{Right}\to \text{Root}$	$\text{Root}\to \text{Right}\to \text{Left}$	Prepend (addFirst) on way down	Swap sides: Go .right in inner loop, .left after pop

Key Changes Explained

1. Recursive Approach

• The Change: result.add(node.val) is moved to the end of the method, after both recursive calls postorder(node.left) and postorder(node.right).
• How It Works: Ensures both left and right child subtrees complete their executions before the parent node’s value is appended to the list.

2. Iterative Stack Approach

• The Change: Three minor symmetric modifications to the Preorder code:

  1. Change result.add() to result.addFirst() (prepend).
  2. Change curr = curr.left to curr = curr.right inside the inner while loop.
  3. Change curr = curr.right to curr = curr.left after stack.pop().

• How It Works: By traversing Right before Left, the nodes are visited in Reverse Postorder ($\text{Root}\to \text{Right}\to \text{Left}$). Prepending each node to the head of the output list automatically reverses this sequence back into standard Postorder ($\text{Left}\to \text{Right}\to \text{Root}$).

3. Morris Traversal Approach

• The Change: Mirroring Morris Preorder:

  1. Look for succ (leftmost child of curr.right) instead of pred (rightmost child of curr.left).
  2. Thread succ.left = curr instead of pred.right = curr.
  3. Prepend addFirst instead of appending add.

• How It Works: Uses the right child links to traverse downward, temporarily wiring the leftmost leaf’s left pointer back to curr. Prepending the output converts the $\text{Root}\to \text{Right}\to \text{Left}$ traversal directly into Postorder without requiring auxiliary stack memory or post-processing reversals.