Postorder Traversal of a Binary Tree using Iteration

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❯

Understanding the Problem

In postorder traversal of a binary tree, the nodes are visited in the order: left subtree → right subtree → root. This is typically done using recursion, but in this solution, we want to implement it iteratively.

The challenge is that postorder is the only traversal where the root is visited after both children, which makes an iterative approach less straightforward compared to preorder or inorder traversals. We need a way to ensure that nodes are processed after their left and right subtrees have been fully traversed.

We will walk through this step-by-step using a concrete example and build up the solution using two stacks to simulate the recursive behavior.

Step-by-Step Solution with Example

Step 1: Choose an Example

Let's take this binary tree as our example:

      1
     /     2   3
   /      4   5   6

Expected postorder traversal: [4, 5, 2, 6, 3, 1]

Step 2: Initialize Two Stacks

We use stack1 for traversal and stack2 to store nodes in postorder reverse format.

Push the root (1) to stack1.

Step 3: Traverse Using stack1

While stack1 is not empty:

Pop a node from stack1 and push it to stack2.
Push the left child of the node (if it exists) to stack1.
Push the right child (if it exists) to stack1.

This effectively processes root-right-left order and stores them in stack2.

Step 4: Collect Postorder from stack2

Finally, pop all elements from stack2 to get them in left-right-root (postorder) order.

From the above tree, the steps will look like:

stack1: [1] → pop 1 → push to stack2
push 2, push 3 → stack1: [2, 3]
pop 3 → push to stack2 → push 6 → stack1: [2, 6]
pop 6 → push to stack2
pop 2 → push to stack2 → push 4, 5 → stack1: [4, 5]
pop 5 → push to stack2, pop 4 → push to stack2

Now stack2 contains: [1, 3, 6, 2, 5, 4]. Reversing gives us the postorder: [4, 5, 2, 6, 3, 1]

Edge Cases

Case 1: Empty Tree

If the root is null, simply return an empty list as there are no nodes to traverse.

Case 2: Single Node Tree

If the tree has only one node, that node is both the root and the only node. The postorder traversal will just return that node.

Case 3: Only Left or Right Subtree

For a skewed tree (e.g., [1,null,2,3]), traversal must still follow left-right-root logic. The iterative two-stack method ensures the correct order even when one side is missing.

Case 4: Full Binary Tree

In trees where every node has 0 or 2 children, the traversal will still work seamlessly, because both children are always processed before the root is added to the result.

Finally

Iterative postorder traversal can be tricky because of the requirement to process the root after both children. Using two stacks simplifies this by reversing a modified preorder traversal. This method is reliable and handles all edge cases, including skewed and full trees.

Always remember: stack2 will give you the correct postorder traversal when you reverse the root-right-left order pushed into it.

Algorithm Steps❯

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

Code

Python

Java

JavaScript

C++

Kotlin

Swift

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))

⬅ Previous TopicPostorder Traversal of a Binary Tree Using Recursion

Next Topic ⮕Level Order Traversal of a Binary Tree using Recursion

Comments

Loading comments...