LeetCode Solutions Blog

Binary Tree Postorder Traversal

Number: 145

Difficulty: Easy

Paid? No

Problem Description

Given the root of a binary tree, return the postorder traversal of its nodes' values. The postorder traversal visits the left subtree, the right subtree, and then the node itself. While the recursive solution is straightforward, the challenge here is to implement it iteratively.

Key Insights

Use an iterative approach to avoid recursion.
A two-stack strategy can reverse the order of node processing to simulate postorder traversal.
One stack can be used too, though the two-stack method is intuitive: first stack for processing nodes, second stack to reverse the order.
Edge case: if the tree is empty, return an empty list.

Space and Time Complexity

Time Complexity: O(n) – Each node is processed once. Space Complexity: O(n) – In worst case, both stacks can contain up to all the nodes in the tree.

Solution

The solution uses a two-stack approach. The first stack is used for traversing the tree in a modified pre-order (root, right, left) such that when nodes are transferred into the second stack, they will be in the postorder (left, right, root) order. Finally, the values in the second stack are collected and returned as the result.

Code Solutions

# 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 the tree is empty, return an empty list.
        if not root:
            return []
            
        # Stack for processing nodes.
        stack1 = [root]
        # Stack to collect nodes in reverse postorder.
        stack2 = []
        # Loop until all nodes are processed.
        while stack1:
            # Pop a node from the first stack.
            node = stack1.pop()
            # Push the node onto the second stack.
            stack2.append(node)
            # Push the left child first (if exists).
            if node.left:
                stack1.append(node.left)
            # Push the right child (if exists).
            if node.right:
                stack1.append(node.right)
                
        # The second stack now contains nodes in reverse of postorder.
        # Extract the node values in proper postorder.
        result = []
        while stack2:
            result.append(stack2.pop().val)
        return result