Inorder Traversal of a Binary Tree using Iteration

Problem Statement❯

You are given the root of a binary tree. Your task is to perform an inorder traversal (left → root → right) of the tree using an iterative approach and return the list of visited node values. Unlike the recursive approach, this solution should avoid using function call stack and instead simulate the process using an explicit stack data structure.

Examples❯

Input Tree	Inorder Traversal Output	Description
[1, 2, 3, 4, 5, null, 6]	[4, 2, 5, 1, 3, 6]	Standard case: Tree with both left and right children and missing node
[1]	[1]	Edge case: Tree with a single node
[]	[]	Edge case: Empty tree with no nodes
[1, 2, null, 3, null, null, null, 4]	[4, 3, 2, 1]	Edge case: Deep left-skewed tree
[1, null, 2, null, null, null, 3]	[1, 2, 3]	Edge case: Deep right-skewed tree
[5, 3, 7, 2, 4, 6, 8]	[2, 3, 4, 5, 6, 7, 8]	Balanced binary search tree (BST): inorder gives sorted values

Visualization Player

Solution❯

Understanding the Problem

Inorder traversal is a common way to visit all the nodes in a binary tree. The order of traversal is: Left subtree → Node → Right subtree. When done recursively, it’s straightforward. But when we try to do it iteratively, we need to simulate the call stack manually using a data structure — typically a stack.

Our goal is to traverse the binary tree in inorder sequence using an iterative approach, even in complex or edge structures like skewed trees or empty trees.

Step-by-Step Solution with Example

Step 1: Use a Stack to Simulate Recursion

We use a stack to keep track of nodes while going left. This mimics the call stack of a recursive solution. We keep pushing nodes onto the stack as we go left.

Step 2: Start from the Root

Initialize a stack, and set the current pointer to the root. As long as the current node is not null, push it onto the stack and move left.

Step 3: Process the Leftmost Node

Once current becomes null, we pop a node from the stack — this is the node we visit next. Add its value to the result list.

Step 4: Move to the Right Subtree

After visiting a node, move the current pointer to its right child. Repeat the process — push all left children of the new current onto the stack.

Step 5: Loop Until Done

Repeat steps 2–4 until the stack is empty and the current pointer is null. This ensures all nodes are visited in inorder.

Example Walkthrough


Given binary tree:
      1
     /     2   3
   /   4   5

Inorder traversal: [4, 2, 5, 1, 3]

Steps:
- Start at root (1), push to stack → go left to 2 → push → go left to 4 → push → no more left.
- Pop 4, visit it → move to null → pop 2, visit it → move to right (5)
- Push 5 → no left → pop and visit 5 → move to null
- Pop 1, visit it → move to right (3) → push → no left → pop and visit
Final output: [4, 2, 5, 1, 3]

Edge Cases

Left-Skewed Tree

Example: 4 → 3 → 2 → 1 (all nodes only have left children). We keep pushing nodes until we reach null, then pop and visit nodes bottom-up. Result is: [1, 2, 3, 4]

Right-Skewed Tree

Example: 1 → 2 → 3 → 4 (only right children). There are no left nodes to push, so we visit the node directly and move to the right. Result is: [1, 2, 3, 4]

Single Node Tree

Only root node exists. We visit it, and there are no left or right children. Output is simply: [node.val]

Empty Tree

If the root is null, then there are no nodes to traverse. Return an empty list. This must be handled explicitly to avoid null reference errors.

Finally

Inorder traversal using iteration may seem tricky at first, but with a stack and a pointer to current node, it becomes intuitive. Always remember: push while going left, pop and visit when you hit null, then move right. Understanding the structure of the tree and edge cases ensures a robust and error-free solution.

Algorithm Steps❯

Start with the root node of the binary tree.
Initialize an empty stack and set the current node as the root.
While the current node is not null or the stack is not empty, do:
Push the current node onto the stack and move to its left child until the current node is null.
When the current node is null, pop a node from the stack, record its value, and set the current node to its right child.
Repeat until both the current node is null and the stack is empty.

Code

C++

Python

Java

Rust

Kotlin

Swift

#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* inorderTraversal(TreeNode* root, int* returnSize) {
    int* result = malloc(100 * sizeof(int));
    TreeNode** stack = malloc(100 * sizeof(TreeNode*));
    int top = -1, index = 0;
    TreeNode* current = root;
    while (current || top >= 0) {
        while (current) {
            stack[++top] = current;
            current = current->left;
        }
        current = stack[top--];
        result[index++] = current->val;
        current = current->right;
    }
    *returnSize = index;
    free(stack);
    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 = inorderTraversal(root, &returnSize);
    for (int i = 0; i < returnSize; i++) {
        printf("%d ", res[i]);
    }
    printf("\n");
    free(res);
    return 0;
}

⬅ Previous TopicInorder Traversal of a Binary Tree using Recursion

Next Topic ⮕Postorder Traversal of a Binary Tree Using Recursion

Comments

Loading comments...