We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

Binary Tree Postorder Traversal

Difficulty: Easy

Problem Description

Given the root of a binary tree, return the postorder traversal of its nodes' values.

Key Insights

Postorder traversal visits the left subtree, then the right subtree, and finally the root node.
A recursive approach is straightforward but can lead to stack overflow for deep trees; an iterative approach using a stack can avoid this issue.
The iterative approach can utilize a stack to simulate the recursive function call stack.

Space and Time Complexity

Time Complexity: O(n) - Each node is visited once. Space Complexity: O(n) - The stack can hold up to n nodes in the worst case.

Solution

To solve the problem iteratively, we use a stack to keep track of nodes to visit. The algorithm works as follows:

Initialize an empty stack and a list to store the postorder traversal.
Push the root node onto the stack.
While the stack is not empty:
- Pop a node from the stack and add its value to the result list.
- Push the left and right children of the node onto the stack (if they exist).
Finally, reverse the result list since we added the nodes in root-right-left order.

This approach ensures we traverse all nodes and collect their values in the correct postorder sequence.

Code Solutions

def postorderTraversal(root):
    if not root:
        return []
    
    stack = [root]
    output = []
    
    while stack:
        node = stack.pop()
        output.append(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    
    return output[::-1]  # Reverse the output for postorder

← Back to All Questions