LeetCode 145 - Binary Tree Postorder Traversal

LeetCode Problem 145

Difficulty: 🟢 Easy
Topics: Stack, Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

The problem asks us to return the postorder traversal of a binary tree.

A binary tree is made of nodes, where each node contains:

A value
A pointer to a left child
A pointer to a right child

In postorder traversal, we must visit nodes in this exact order:

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

This ordering is important because the node itself is processed only after both of its children have already been processed.

For example, consider the tree:

The traversal order becomes:

Visit left subtree of 1, which is empty
Visit right subtree rooted at 2
Visit left subtree rooted at 3
Visit right subtree of 2, which is empty
Visit node 2
Visit node 1

Result:

[3, 2, 1]

The input is given as the root node of the binary tree. The output should be a list containing node values in postorder sequence.

The constraints are small, at most 100 nodes, so even recursive solutions easily fit within recursion depth limits in most languages. However, the follow up specifically asks for an iterative solution, meaning we should understand how to simulate recursion manually using a stack.

Several edge cases are important:

The tree may be empty, meaning root = []
The tree may contain only one node
The tree may be completely skewed to the left or right
Nodes may contain negative values
Some children may be null while others exist

A naive implementation can easily produce incorrect ordering if it visits the current node too early. Postorder traversal requires delaying node processing until after both subtrees are finished.

Approaches

Brute Force Approach, Recursive DFS

The simplest solution uses recursion.

At each node:

Recursively traverse the left subtree
Recursively traverse the right subtree
Append the current node's value to the result

This works naturally because the function call stack automatically remembers where to return after each subtree finishes. The recursive structure mirrors the definition of postorder traversal itself.

This approach is correct because every node is processed only after its left and right descendants have already been processed.

Although the problem constraints are small, recursion uses implicit stack space proportional to the tree height. The follow up also explicitly asks whether we can do it iteratively, meaning we should understand how to replace the recursive call stack with an explicit stack data structure.

Optimal Approach, Iterative DFS Using a Stack

The iterative approach simulates recursion manually using a stack.

One common technique is:

Process nodes in modified preorder order:
Root
Right
Left
Store visited values
Reverse the final result

Why does this work?

Normal preorder traversal is:

Root -> Left -> Right

If we instead traverse:

Root -> Right -> Left

and reverse the result afterward, we get:

Left -> Right -> Root

which is exactly postorder traversal.

This method is elegant because it avoids complicated state tracking. The stack naturally handles traversal order, and reversing the result produces the desired sequence.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(h)	Recursive DFS using call stack
Optimal	O(n)	O(n)	Iterative DFS using explicit stack and result reversal

Here:

n is the number of nodes
h is the height of the tree

Algorithm Walkthrough

Iterative Postorder Traversal

Create an empty result list.

This list will temporarily store nodes in modified preorder order. 2. Handle the empty tree case.

If the root is None, immediately return an empty list. 3. Initialize a stack with the root node.

The stack simulates recursive DFS traversal. 4. While the stack is not empty, continue processing nodes.

Each iteration processes one node from the stack. 5. Pop the top node from the stack.

This node becomes the current node being processed. 6. Append the current node's value to the result list.

We intentionally process the node before its children. This produces:

Root -> Right -> Left

Push the left child onto the stack if it exists.

We push left first because stacks are LIFO. This ensures the right child gets processed before the left child. 8. Push the right child onto the stack if it exists.

Since the right child is pushed last, it is processed first. 9. After traversal finishes, reverse the result list.

The traversal order generated was:

Root -> Right -> Left

Reversing gives:

Left -> Right -> Root

which is the correct postorder traversal. 10. Return the reversed result list.

Why it works

The algorithm guarantees correctness because every node is visited before its children in the temporary order. Reversing that order ensures each node appears after both its left and right subtrees, exactly matching the definition of postorder traversal.

The stack ensures every node is processed exactly once, and reversing transforms the modified preorder traversal into true postorder traversal.

Python Solution

# 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]:
        if not root:
            return []

        result = []
        stack = [root]

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

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

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

        return result[::-1]

The implementation begins by handling the empty tree case. If the root is None, the traversal result is simply an empty list.

A stack is initialized with the root node. The stack controls traversal order and replaces recursive function calls.

Inside the loop, we repeatedly pop nodes from the stack and append their values to the result list. The key detail is the order in which children are pushed:

Left child first
Right child second

Because stacks are last-in-first-out, the right child gets processed before the left child.

This produces a traversal order of:

Root -> Right -> Left

Finally, the result list is reversed to obtain:

Left -> Right -> Root

which is the required postorder traversal.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func postorderTraversal(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }

    result := []int{}
    stack := []*TreeNode{root}

    for len(stack) > 0 {
        n := len(stack) - 1
        node := stack[n]
        stack = stack[:n]

        result = append(result, node.Val)

        if node.Left != nil {
            stack = append(stack, node.Left)
        }

        if node.Right != nil {
            stack = append(stack, node.Right)
        }
    }

    // Reverse result
    left, right := 0, len(result)-1
    for left < right {
        result[left], result[right] = result[right], result[left]
        left++
        right--
    }

    return result
}

The Go implementation follows the same logic as the Python version.

Go uses slices for both the stack and the result list. Since Go does not provide built-in stack structures, the stack is implemented using slice append and slicing operations.

Unlike Python's [::-1], Go requires manually reversing the slice using two pointers.

The empty tree case returns an empty slice instead of nil, which matches expected LeetCode behavior.

Worked Examples

Example 1

Input:

root = [1,null,2,3]

Tree:

Initial state:

Step	Stack	Result
Start	[1]	[]

Process node 1:

Step	Stack	Result
Pop 1	[]	[1]
Push right child 2	[2]	[1]

Process node 2:

Step	Stack	Result
Pop 2	[]	[1,2]
Push left child 3	[3]	[1,2]

Process node 3:

Step	Stack	Result
Pop 3	[]	[1,2,3]

Reverse result:

[3,2,1]

Example 2

Input:

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

Traversal progression:

Step	Node Processed	Result Before Reverse
1	1	[1]
2	3	[1,3]
3	8	[1,3,8]
4	9	[1,3,8,9]
5	2	[1,3,8,9,2]
6	5	[1,3,8,9,2,5]
7	7	[1,3,8,9,2,5,7]
8	6	[1,3,8,9,2,5,7,6]
9	4	[1,3,8,9,2,5,7,6,4]

Reverse result:

[4,6,7,5,2,9,8,3,1]

Example 3

Input:

root = []

Initial check:

root is None

Return:

[]

Example 4

Input:

root = [1]

Initial state:

Step	Stack	Result
Start	[1]	[]

Process node 1:

Step	Stack	Result
Pop 1	[]	[1]

Reverse result:

[1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every node is pushed and popped exactly once
Space	O(n)	Stack and result list may store all nodes

The traversal visits every node exactly once, so the time complexity is linear in the number of nodes.

The space complexity comes from two structures:

The explicit stack
The result list

In the worst case, both may contain up to n nodes simultaneously, especially for highly skewed trees.

Test Cases

# Helper TreeNode class
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):
        if not root:
            return []

        result = []
        stack = [root]

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

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

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

        return result[::-1]

sol = Solution()

# Empty tree
assert sol.postorderTraversal(None) == []  # tests empty input

# Single node
root = TreeNode(1)
assert sol.postorderTraversal(root) == [1]  # tests single element tree

# Example 1
root = TreeNode(1)
root.right = TreeNode(2)
root.right.left = TreeNode(3)
assert sol.postorderTraversal(root) == [3, 2, 1]  # tests mixed children

# Left-skewed tree
root = TreeNode(1,
    TreeNode(2,
        TreeNode(3,
            TreeNode(4)
        )
    )
)
assert sol.postorderTraversal(root) == [4, 3, 2, 1]  # tests deep left chain

# Right-skewed tree
root = TreeNode(1)
root.right = TreeNode(2)
root.right.right = TreeNode(3)
root.right.right.right = TreeNode(4)
assert sol.postorderTraversal(root) == [4, 3, 2, 1]  # tests deep right chain

# Full binary tree
root = TreeNode(1,
    TreeNode(2,
        TreeNode(4),
        TreeNode(5)
    ),
    TreeNode(3,
        TreeNode(6),
        TreeNode(7)
    )
)
assert sol.postorderTraversal(root) == [4, 5, 2, 6, 7, 3, 1]  # tests balanced tree

# Tree with negative values
root = TreeNode(-1,
    TreeNode(-2),
    TreeNode(-3)
)
assert sol.postorderTraversal(root) == [-2, -3, -1]  # tests negative numbers

# Tree with missing children
root = TreeNode(1)
root.left = TreeNode(2)
root.left.right = TreeNode(3)
assert sol.postorderTraversal(root) == [3, 2, 1]  # tests sparse tree

Test Summary

Test	Why
Empty tree	Verifies handling of `None` input
Single node	Verifies smallest non-empty tree
Example 1	Verifies standard postorder behavior
Left-skewed tree	Tests deep recursion-like structure
Right-skewed tree	Tests traversal ordering correctness
Full binary tree	Verifies balanced subtree processing
Negative values	Ensures values do not affect traversal
Sparse tree	Tests handling of missing children

Edge Cases

Empty Tree

An empty tree is represented by root = None. This is a common source of bugs because traversal loops may assume the root exists and attempt to access attributes like root.left.

The implementation handles this immediately with:

if not root:
    return []

This guarantees safe behavior and returns the correct empty traversal.

Single Node Tree

A tree with only one node has no children. Some implementations incorrectly attempt subtree traversal without checking for None.

In this case:

The node is added to the result
No children are pushed onto the stack
Reversing a one-element list leaves it unchanged

The algorithm correctly returns [node.val].

Highly Skewed Trees

A tree may resemble a linked list, either entirely left-skewed or right-skewed.

For example:

These cases are important because traversal ordering becomes easier to break accidentally.

The stack-based implementation correctly processes nodes in modified preorder order and reverses the result at the end, ensuring proper postorder traversal regardless of tree shape.

Trees with Missing Children

Some nodes may have only one child.

Example:

Naive implementations may incorrectly assume both children exist.

The implementation explicitly checks:

if node.left:

and

if node.right:

before pushing children onto the stack, preventing invalid accesses while preserving correct traversal order.