LeetCode 145: Binary Tree Postorder Traversal

Problem Restatement

We are given the root of a binary tree.

Return the postorder traversal of its node values.

Postorder traversal visits nodes in this order:

left subtree -> right subtree -> root

If the tree is empty, return an empty list.

LeetCode also includes a follow-up asking for an iterative solution. (leetcode.com)

Examples

Example 1:

Traversal order:

visit left of 1: none
visit right subtree rooted at 2
visit left of 2: 3
visit right of 2: none
visit 2
visit 1

Output:

[3, 2, 1]

Example 2:

root = []

Output:

[]

Example 3:

root = [1]

Output:

[1]

Input and Output

Item	Meaning
Input	`root: Optional[TreeNode]`
Output	`list[int]`
Traversal order	Left subtree, right subtree, root
Empty tree	Return `[]`

Function shape:

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> list[int]:
        ...

Core Idea

Postorder traversal processes children before the current node.

At every node:

Traverse the left subtree.
Traverse the right subtree.
Visit the current node.

So the recursive structure directly follows the traversal definition:

postorder(node.left)
postorder(node.right)
visit(node)

Recursive Algorithm

Create an empty result list.

Define:

dfs(node)

For each node:

If the node is None, return.
Traverse the left subtree.
Traverse the right subtree.
Append the current node value.

Return the result list.

Correctness

For any subtree rooted at node, postorder traversal requires processing:

all nodes in the left subtree
all nodes in the right subtree
the root node last

The algorithm recursively traverses the left subtree first, producing the left subtree in postorder.

Then it recursively traverses the right subtree, producing the right subtree in postorder.

Finally, it appends the current node value.

Therefore, every subtree is processed in left-right-root order, which is exactly postorder traversal.

If the tree is empty, the helper immediately returns and the result list remains empty.

Thus, the algorithm correctly returns the postorder traversal of the tree.

Complexity

Let:

Symbol	Meaning
`n`	Number of nodes
`h`	Height of the tree

Metric	Value	Why
Time	`O(n)`	Each node is visited once
Space	`O(h)`	Recursion stack depth

In the worst case, a skewed tree has height n.

Recursive Implementation

from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> list[int]:
        result = []

        def dfs(node: Optional[TreeNode]) -> None:
            if node is None:
                return

            dfs(node.left)
            dfs(node.right)
            result.append(node.val)

        dfs(root)
        return result

Code Explanation

The traversal result is stored in:

result = []

The helper processes one subtree:

def dfs(node: Optional[TreeNode]) -> None:

The base case:

if node is None:
    return

stops recursion at missing children.

Postorder visits the left subtree first:

dfs(node.left)

Then the right subtree:

dfs(node.right)

Finally, visit the root:

result.append(node.val)

After the traversal finishes:

return result

returns the full postorder sequence.

Iterative Solution

Postorder is trickier iteratively because the root must be processed last.

One elegant trick:

Perform modified preorder traversal:
- root
- right
- left
Reverse the result.

Why?

Normal preorder:

root -> left -> right

Modified preorder:

root -> right -> left

Reverse it:

left -> right -> root

which is postorder.

Iterative Implementation

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> list[int]:
        if root is None:
            return []

        result = []
        stack = [root]

        while stack:
            node = stack.pop()
            result.append(node.val)

            if node.left is not None:
                stack.append(node.left)

            if node.right is not None:
                stack.append(node.right)

        return result[::-1]

Iterative Code Explanation

Start with the root:

stack = [root]

Each iteration:

node = stack.pop()

visits the current node:

result.append(node.val)

Push the left child first:

if node.left is not None:
    stack.append(node.left)

Then the right child:

if node.right is not None:
    stack.append(node.right)

Because the stack is LIFO, the right child is processed before the left child.

So traversal order becomes:

root -> right -> left

Finally:

return result[::-1]

reverses it into:

left -> right -> root

which is postorder traversal.

Alternative Iterative Method with Visited State

Another iterative approach uses explicit traversal state.

Each stack item stores:

(node, visited)

If visited is false:

push the node back as visited
push right child
push left child

If visited is true:

append node value

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> list[int]:
        if root is None:
            return []

        result = []
        stack = [(root, False)]

        while stack:
            node, visited = stack.pop()

            if visited:
                result.append(node.val)
                continue

            stack.append((node, True))

            if node.right:
                stack.append((node.right, False))

            if node.left:
                stack.append((node.left, False))

        return result

This follows the recursive structure more directly.

Testing

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def run_tests():
    s = Solution()

    root = TreeNode(1, None, TreeNode(2, TreeNode(3)))
    assert s.postorderTraversal(root) == [3, 2, 1]

    assert s.postorderTraversal(None) == []

    root = TreeNode(1)
    assert s.postorderTraversal(root) == [1]

    root = TreeNode(
        1,
        TreeNode(2, TreeNode(4), TreeNode(5)),
        TreeNode(3),
    )
    assert s.postorderTraversal(root) == [4, 5, 2, 3, 1]

    root = TreeNode(1, TreeNode(2, TreeNode(3)))
    assert s.postorderTraversal(root) == [3, 2, 1]

    root = TreeNode(1, None, TreeNode(2, None, TreeNode(3)))
    assert s.postorderTraversal(root) == [3, 2, 1]

    print("all tests passed")

run_tests()

Test meaning:

Test	Why
Standard LeetCode example	Mixed left/right structure
Empty tree	Returns empty list
Single node	Smallest non-empty tree
Full tree	Confirms left-right-root ordering
Left-skewed tree	Deep recursive left traversal
Right-skewed tree	Deep recursive right traversal