Binary Tree Postorder Traversal

Difficulty: Easy

Problem

Given the root of a binary tree, list its node values in postorder: left subtree first, then right subtree, then the node itself. Put another way, a node is only recorded once everything beneath it has been recorded.

Example

Input: root = [1,2,3,4,5]
Output: [4,5,2,3,1]
Explanation: Node 2 is recorded after its children 4 and 5, so the left side gives 4, 5, 2. Then the right child 3 is recorded, and the root 1 comes last: [4,5,2,3,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

Base case: if the node is null, return, an empty subtree records nothing
Recursively traverse the ENTIRE left subtree first
Then recursively traverse the ENTIRE right subtree
Only now append the node's own value to the result, visit on departure
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

Pseudocode

function postorderTraversal(root):
    result = []
    
    function postorder(node):
        if node is ____:
            return
        
        postorder(node.____)
        postorder(node.____)
        result.append(node.____)
    
    postorder(root)
    return result

Hints

Base case: which kind of node has nothing to record? (An empty one!)
First recursive call: postorder completely finishes the LEFT subtree before anything else
Second recursive call: then the whole RIGHT subtree. The current node is still waiting silently
The append comes last: only after both calls return does the node record its own value

Complexity questions

What is the time complexity of postorder traversal on a tree with n nodes?

O(n). Every node is visited exactly once, and each visit does O(1) work. Dispatch two recursive calls and append one value. Total: O(n).

What is the space complexity of the recursive solution (not counting the output list)?

O(h): the recursion call stack, where h is the tree height. Recursion isn't free: the call stack grows as deep as the tree. That's O(h): around O(log n) for a nicely balanced tree, but O(n) for a completely skewed one that's really a linked list in disguise.

You want to compute the SIZE of every subtree (how many nodes live under each node, including itself). Why is postorder the right order?

Because a node's size = 1 + left size + right size, and the children's sizes must be known FIRST. size(node) = 1 + size(left) + size(right). The inputs to that formula come from the children, so the children must finish before the parent can compute. That's exactly the guarantee postorder gives, and it's the same pattern behind folder sizes on a disk.

Which traversal order should you use to safely delete every node in a tree, and why?

Postorder: a node is freed only after both of its children are already freed. Delete a parent first (preorder-style) and you destroy the .left and .right pointers that are your ONLY way to reach its children, orphaning them in memory. Postorder frees the children first, so by the time the parent's turn comes, nothing beneath it is still needed.

Check your understanding of Binary Tree Postorder Traversal

In postorder traversal, in what order do we handle a node and its two subtrees?

Left → Right → Root. Postorder means the root comes POST, after, everything else: finish the entire left subtree, then the entire right subtree, and only then visit the node itself. Root→Left→Right is preorder, and Left→Root→Right is inorder, same walk, different visit moment.

What is the postorder traversal of [1,null,2,3] (root 1, right child 2, and 2's left child 3)?

[3,2,1]. 1's left is empty, so we dive right to 2, then left to 3. Node 3 finishes first, then 2, and 1 comes last → [3,2,1]. Watch out: [1,2,3] is this tree's PREORDER (root stamped on arrival), and [1,3,2] is its INORDER (1 has no left child, so it's visited before its right subtree).

WHEN exactly does postorder visit a node?

Only after BOTH of its subtrees are completely done. Postorder is 'visit on departure': a node is recorded at the very last moment, as we leave it for good with nothing below it left to do. Preorder is the exact opposite, 'visit on arrival', stamping the node the instant we first touch it.

Which real-world task is postorder traversal the classic choice for?

Safely DELETING a whole tree, or computing the size of every folder on a disk. Deleting and aggregating are bottom-up jobs: you can't delete a parent while its children still need it (you'd lose your only pointers to them), and you can't know a folder's size until every subfolder has reported its own. Postorder guarantees children are fully handled before their parent. Sorted printing is inorder's specialty, and top-down copying is preorder's.

In a postorder traversal of ANY non-empty tree, which node is always visited LAST?

The root. The root can only be visited after its entire left subtree AND its entire right subtree are finished, and together, that's every other node in the tree. The root waits for everything, so it always closes the list. (In preorder it's the mirror image: the root is always FIRST.)