Given the root of a binary tree, return the postorder traversal of its nodes’ values. Postorder visits: left → right → root.

Examples

Example 1:

Input: root = [1,null,2,3]
    1
     \
      2
     /
    3
Output: [3,2,1]

Example 2:

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

Example 3:

Input: root = []
Output: []

Constraints

  • The number of nodes is in [0, 100]
  • -100 <= Node.val <= 100

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Recursive DFS (this problem) O(n) O(h) stack Natural for trees and graphs
Iterative DFS (stack) O(n) O(n) Avoid recursion depth limits
DFS with memoization O(n) O(n) Overlapping subproblems on graphs
Backtracking DFS O(2^n) typical O(n) Enumerate choices with pruning

Thinking Process

Postorder visits left → right → root. The tricky part is the iterative version – we must visit both children before the parent.

Iterative Trick: Modified Preorder + Reverse

Preorder is root → left → right. If we change it to root → right → left (push left before right), then reverse the result, we get left → right → root = postorder.

This avoids the complexity of tracking “has the right child been visited?”

Two-Stack / Prev-Pointer Alternative

A more direct iterative approach uses a prev pointer to track whether we’re returning from the right child, but the reverse trick is simpler to implement.

Tree DFS (bottom-up) 3 9 20 15 7 post-order: combine left + right + 1

Approach 1: Recursive – O(n)

Input: root = [1,null,2,3]
Output: [3,2,1]
# Tree:  1
#         \
#          2
#         /
#        3

Solution Explanation

Approach: Recursive DFS (this problem)

Key idea: Postorder visits left → right → root. The tricky part is the iterative version – we must visit both children before the parent.

Walkthrough — input root = [1,null,2,3], expected output [3,2,1]:

  1. Initialize variables from the problem setup.
  2. Apply the main loop / recursion until the condition is met.
  3. Confirm the result matches the expected output.

    Approach 2: Iterative (Modified Preorder + Reverse) – O(n)

Do root → right → left traversal, then reverse the result to get left → right → root.

Input: root = []
Output: []

Time: O(n) Space: O(n) for the output; O(h) for the stack

Approach 3: Iterative (Prev Pointer) – O(n)

Track the previously visited node. Only visit the current node when its right child is null or was just visited.

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

Time: O(n) Space: O(n) for the output; O(h) for the stack

Comparison Across All Three Traversal Orders

Order Visit when Iterative stack trick
Preorder (root→L→R) First encounter Push right then left
Inorder (L→root→R) After left subtree done Go left, pop, visit, go right
Postorder (L→R→root) After both children done Reverse of (root→R→L), or use prev pointer

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Key Takeaways

  • Reverse trick turns postorder into a simple modification of preorder – swap push order and reverse output
  • Prev pointer approach is the “true” iterative postorder – no reversal needed, but harder to get right
  • All three traversal orders share the same O(n) time and O(h) auxiliary space structure

References

Template Reference