Postorder Traversal of a Binary Tree using Iteration

Contents

ProblemExamplesVisualizationSolutionAlgorithmCode

Problem Statement❯

Given the root of a binary tree, return the postorder traversal of its nodes' values using an iterative approach. In postorder traversal, nodes are visited in the order: left subtree, right subtree, and then the node itself.

Examples❯

Input (Tree Structure) Expected Output Explanation
[1, null, 2, null, null, 3]
[3,2,1]Traverse leftmost node (3), then right (2), then root (1).
[] [] Tree is empty, so no traversal output.
[1]
[1] Only one node exists; postorder visits it last.
[1,2,3,4,5,6,7]
[4,5,2,6,7,3,1] Left subtree (4,5,2), right subtree (6,7,3), then root (1).

Visualization Player

Solution❯

Case 1: Tree is empty

If the root node is null, then the binary tree is empty. In this case, the result of the postorder traversal is simply an empty list, since there are no nodes to visit.

Case 2: Tree has only one node

When the binary tree contains a single node, that node is both the root and the only element in the tree. Postorder traversal (left, right, root) visits the root last, but since it's the only node, it is returned directly.

Case 3: Tree has only right or left subtree

For example, in the tree [1,null,2,3], the traversal begins from the root (1), then moves to its right child (2), and further left to (3). Since postorder is left-right-root, we collect 3 first, then 2, and finally 1. Iterative traversal using two stacks helps in managing this reverse processing efficiently.

Case 4: Tree is a full binary tree

In a full binary tree, where each node has 0 or 2 children (e.g., [1,2,3,4,5,6,7]), postorder traversal recursively processes all left subtree nodes, then right subtree nodes, and finally the root. The iterative approach simulates this recursion using two stacks. The first stack handles the traversal and the second one reverses the node processing order. For the given tree, the left subtree returns [4,5,2], the right subtree returns [6,7,3], and the root 1 comes at the end — resulting in [4,5,2,6,7,3,1].

Why use two stacks in iteration?

Unlike inorder or preorder traversals, postorder is tricky to achieve in a single pass using one stack, because the root has to be processed after both subtrees. The two-stack approach ensures that when we pop from the second stack, we get nodes in the desired left-right-root order. It simulates the call stack behavior of recursive postorder traversal in an explicit, manageable way.

Algorithm Steps❯

  1. Start with the root node of the binary tree.
  2. If the tree is empty, return an empty result.
  3. Initialize two stacks, stack1 and stack2.
  4. Push the root node onto stack1.
  5. While stack1 is not empty, pop a node from it and push that node onto stack2.
  6. If the popped node has a left child, push it onto stack1; if it has a right child, push it onto stack1.
  7. After processing all nodes, pop all nodes from stack2 and record their values. This produces the postorder traversal.

Code

Python
Java
JavaScript
C
C++
C#
Kotlin
Swift
Go
Php
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def postorderTraversal(root):
    if not root:
        return []
    stack1, stack2 = [root], []
    while stack1:
        node = stack1.pop()
        stack2.append(node)
        if node.left:
            stack1.append(node.left)
        if node.right:
            stack1.append(node.right)
    result = []
    while stack2:
        result.append(stack2.pop().val)
    return result

# Example usage:
if __name__ == '__main__':
    # Construct binary tree:
    #        1
    #       / \
    #      2   3
    #     / \
    #    4   5
    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
    print(postorderTraversal(root))