Binary Tree Postorder Traversal

Difficulty: Easy

Problem

Given the root of a binary tree, return the postorder traversal of its nodes' values: Left subtree → Right subtree → Root. A node is visited only AFTER both of its subtrees are completely finished — it's the traversal where every child reports before its parent.

Example

Input: root = [1,null,2,3]
Output: [3,2,1]
Explanation: Start at 1: its left is empty, so dive right to 2. At 2: dive left to 3. Node 3 has no children, so it finishes first and is visited. Back at 2, its right is empty, so 2 is visited next. Finally, with both subtrees done, 1 is visited last → [3,2,1].

Brute-force approach

There is no meaningful 'brute force vs optimal' split here — the recursive traversal IS the natural solution. Trees skip straight to the optimal approach.

Optimal approach

Key insight: It's the same DFS skeleton as preorder and inorder — but the visit line moves AFTER both recursive calls. That one placement makes every parent wait for its children, so the root, waiting for everyone, comes last.

Recursively walk the tree: completely finish the left subtree, then completely finish the right subtree, and only then append the node's own value. Every parent automatically waits for all of its children.

Steps

  1. Base case: if the node is null, return — an empty subtree records nothing
  2. Recursively traverse the ENTIRE left subtree first
  3. Then recursively traverse the ENTIRE right subtree
  4. Only now append the node's own value to the result — visit on departure
  5. Kick off the helper from the root and return the result list

Time complexity: O(n) · Space complexity: O(h) where h = height of tree