ProgramGuru

Postorder Traversal of a Binary Tree using Iteration

Problem and examples

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

Explore Postorder Traversal of a Binary Tree - Iteration

Load an example or enter your own input. Use the player controls to follow each change.

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.

  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.

Implementation and efficiency

C implementation

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

int* postorderTraversal(TreeNode* root, int* returnSize) {
    if (!root) {
        *returnSize = 0;
        return NULL;
    }
    TreeNode** stack1 = malloc(100 * sizeof(TreeNode*));
    TreeNode** stack2 = malloc(100 * sizeof(TreeNode*));
    int top1 = -1, top2 = -1;
    stack1[++top1] = root;
    while (top1 >= 0) {
        TreeNode* node = stack1[top1--];
        stack2[++top2] = node;
        if (node->left) stack1[++top1] = node->left;
        if (node->right) stack1[++top1] = node->right;
    }
    int* result = malloc(100 * sizeof(int));
    int index = 0;
    while (top2 >= 0) {
        result[index++] = stack2[top2--]->val;
    }
    *returnSize = index;
    free(stack1);
    free(stack2);
    return result;
}

int main() {
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    int returnSize;
    int* res = postorderTraversal(root, &returnSize);
    printf("Postorder Traversal: ");
    for (int i = 0; i < returnSize; i++) {
        printf("%d ", res[i]);
    }
    printf("\n");
    free(res);
    return 0;
}

C++ implementation

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> result;
    if (!root) return result;
    stack<TreeNode*> s1, s2;
    s1.push(root);
    while (!s1.empty()) {
        TreeNode* node = s1.top(); s1.pop();
        s2.push(node);
        if (node->left) s1.push(node->left);
        if (node->right) s1.push(node->right);
    }
    while (!s2.empty()) {
        result.push_back(s2.top()->val); s2.pop();
    }
    return result;
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    vector<int> res = postorderTraversal(root);
    cout << "Postorder Traversal: ";
    for (int val : res) cout << val << " ";
    cout << endl;
    return 0;
}

Python implementation

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)
    return [node.val for node in reversed(stack2)]

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

Java implementation

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

public class Postorder {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();
        s1.push(root);
        while (!s1.isEmpty()) {
            TreeNode node = s1.pop();
            s2.push(node);
            if (node.left != null) s1.push(node.left);
            if (node.right != null) s1.push(node.right);
        }
        while (!s2.isEmpty()) res.add(s2.pop().val);
        return res;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        Postorder sol = new Postorder();
        System.out.println(sol.postorderTraversal(root));
    }
}

JavaScript implementation

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function postorderTraversal(root) {
    if (!root) return [];
    const stack1 = [root], stack2 = [];
    while (stack1.length) {
        const node = stack1.pop();
        stack2.push(node);
        if (node.left) stack1.push(node.left);
        if (node.right) stack1.push(node.right);
    }
    return stack2.reverse().map(node => node.val);
}

const root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3));
console.log(postorderTraversal(root));

Go implementation

package main

import (
    "fmt"
)

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

func postorderTraversal(root *TreeNode) []int {
    if root == nil {
        return []int{}
    }
    stack1 := []*TreeNode{root}
    stack2 := []*TreeNode{}
    for len(stack1) > 0 {
        node := stack1[len(stack1)-1]
        stack1 = stack1[:len(stack1)-1]
        stack2 = append(stack2, node)
        if node.Left != nil {
            stack1 = append(stack1, node.Left)
        }
        if node.Right != nil {
            stack1 = append(stack1, node.Right)
        }
    }
    result := []int{}
    for i := len(stack2) - 1; i >= 0; i-- {
        result = append(result, stack2[i].Val)
    }
    return result
}

func main() {
    root := &TreeNode{1, &TreeNode{2, &TreeNode{4, nil, nil}, &TreeNode{5, nil, nil}}, &TreeNode{3, nil, nil}}
    fmt.Println("Postorder Traversal:", postorderTraversal(root))
}

Rust implementation

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

impl TreeNode {
    fn new(val: i32) -> Self {
        TreeNode { val, left: None, right: None }
    }
}

fn postorder_traversal(root: Option<Box<TreeNode>>) -> Vec<i32> {
    let mut res = vec![];
    let mut s1 = vec![];
    let mut s2 = vec![];
    if let Some(node) = root {
        s1.push(node);
    }
    while let Some(node) = s1.pop() {
        if let Some(ref left) = node.left {
            s1.push(left.clone());
        }
        if let Some(ref right) = node.right {
            s1.push(right.clone());
        }
        s2.push(node.val);
    }
    s2.reverse();
    s2
}

fn main() {
    let root = Some(Box::new(TreeNode {
        val: 1,
        left: Some(Box::new(TreeNode {
            val: 2,
            left: Some(Box::new(TreeNode::new(4))),
            right: Some(Box::new(TreeNode::new(5)),
        })),
        right: Some(Box::new(TreeNode::new(3))),
    }));
    println!("{:?}", postorder_traversal(root));
}

Kotlin implementation

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun postorderTraversal(root: TreeNode?): List<Int> {
    val stack1 = mutableListOf<TreeNode>()
    val stack2 = mutableListOf<TreeNode>()
    val result = mutableListOf<Int>()
    if (root == null) return result
    stack1.add(root)
    while (stack1.isNotEmpty()) {
        val node = stack1.removeAt(stack1.size - 1)
        stack2.add(node)
        node.left?.let { stack1.add(it) }
        node.right?.let { stack1.add(it) }
    }
    while (stack2.isNotEmpty()) {
        result.add(stack2.removeAt(stack2.size - 1).`val`)
    }
    return result
}

fun main() {
    val root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left!!.left = TreeNode(4)
    root.left!!.right = TreeNode(5)
    println(postorderTraversal(root))
}

Swift implementation

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
}

func postorderTraversal(_ root: TreeNode?) -> [Int] {
    guard let root = root else { return [] }
    var stack1: [TreeNode] = [root]
    var stack2: [TreeNode] = []
    while !stack1.isEmpty {
        let node = stack1.removeLast()
        stack2.append(node)
        if let left = node.left { stack1.append(left) }
        if let right = node.right { stack1.append(right) }
    }
    return stack2.reversed().map { $0.val }
}

let root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left!.left = TreeNode(4)
root.left!.right = TreeNode(5)
print(postorderTraversal(root))

TypeScript implementation

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function postorderTraversal(root: TreeNode | null): number[] {
    if (!root) return [];
    const stack1: TreeNode[] = [root];
    const stack2: TreeNode[] = [];
    while (stack1.length > 0) {
        const node = stack1.pop()!;
        stack2.push(node);
        if (node.left) stack1.push(node.left);
        if (node.right) stack1.push(node.right);
    }
    return stack2.reverse().map(node => node.val);
}

const root = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3));
console.log(postorderTraversal(root));