ProgramGuru

Inorder Traversal of a Binary Tree using Iteration

Problem and examples

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

Explore Inorder 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

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.

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

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* 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;
}

C++ implementation

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

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

void inorderTraversal(TreeNode* root) {
    stack<TreeNode*> st;
    TreeNode* current = root;
    while (current || !st.empty()) {
        while (current) {
            st.push(current);
            current = current->left;
        }
        current = st.top();
        st.pop();
        cout << current->val << " ";
        current = current->right;
    }
}

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);
    inorderTraversal(root);
    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 inorderTraversal(root):
    result = []
    stack = []
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.val)
        current = current.right
    return result

if __name__ == '__main__':
    root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
    print(inorderTraversal(root))

Java implementation

import java.util.*;

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

public class IterativeInorderTraversal {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();
            result.add(current.val);
            current = current.right;
        }
        return result;
    }

    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);
        IterativeInorderTraversal sol = new IterativeInorderTraversal();
        System.out.println(sol.inorderTraversal(root));
    }
}

JavaScript implementation

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

function inorderTraversal(root) {
    const result = [];
    const stack = [];
    let current = root;
    while (current || stack.length) {
        while (current) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        result.push(current.val);
        current = current.right;
    }
    return result;
}

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

Go implementation

package main

import (
    "fmt"
)

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

func inorderTraversal(root *TreeNode) []int {
    var result []int
    stack := []*TreeNode{}
    current := root
    for current != nil || len(stack) > 0 {
        for current != nil {
            stack = append(stack, current)
            current = current.Left
        }
        current = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        result = append(result, current.Val)
        current = current.Right
    }
    return result
}

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

Rust implementation

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<Rc<RefCell<TreeNode>>>,
    right: Option<Rc<RefCell<TreeNode>>>,
}

fn inorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
    let mut result = vec![];
    let mut stack = vec![];
    let mut current = root;
    while current.is_some() || !stack.is_empty() {
        while let Some(node) = current {
            stack.push(Rc::clone(&node));
            current = node.borrow().left.clone();
        }
        current = stack.pop();
        if let Some(node) = current {
            result.push(node.borrow().val);
            current = node.borrow().right.clone();
        }
    }
    result
}

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

Kotlin implementation

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

fun inorderTraversal(root: TreeNode?): List<Int> {
    val result = mutableListOf<Int>()
    val stack = ArrayDeque<TreeNode>()
    var current = root
    while (current != null || stack.isNotEmpty()) {
        while (current != null) {
            stack.addFirst(current)
            current = current.left
        }
        current = stack.removeFirst()
        result.add(current.`val`)
        current = current.right
    }
    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(inorderTraversal(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 inorderTraversal(_ root: TreeNode?) -> [Int] {
    var result = [Int]()
    var stack = [TreeNode]()
    var current = root
    while current != nil || !stack.isEmpty {
        while let node = current {
            stack.append(node)
            current = node.left
        }
        current = stack.removeLast()
        if let node = current {
            result.append(node.val)
            current = node.right
        }
    }
    return result
}

let root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left!.left = TreeNode(4)
root.left!.right = TreeNode(5)
print(inorderTraversal(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 inorderTraversal(root: TreeNode | null): number[] {
    const result: number[] = [];
    const stack: TreeNode[] = [];
    let current: TreeNode | null = root;
    while (current || stack.length > 0) {
        while (current) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop()!;
        result.push(current.val);
        current = current.right;
    }
    return result;
}

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