Course contentsShow
← Computer Science
Lesson 481 of 2,87211. Binary TreesFree lesson

Iterative Inorder with Stack

Implementing inorder iteratively: traverse left while pushing, pop when null, process, move right, repeat.

Iterative Inorder with Stack

You'll learn how to perform inorder traversal without recursion by manually managing a stack to track your position in the tree.

The Core Idea

In recursive inorder, the call stack automatically remembers where you are while you explore left subtrees. To do this iteratively, you explicitly use a stack data structure to simulate that behavior.

The pattern follows these steps:

  1. Go left as far as possible, pushing each node onto the stack
  2. When you can't go left anymore (hit null), pop from the stack
  3. Process that popped node (print it, collect it, etc.)
  4. Move to its right child and repeat

Think of it like exploring a maze: you keep going left, leaving breadcrumbs (the stack) so you can backtrack when you hit a dead-end, then try the right path.

Why This Works

The stack holds nodes whose left subtrees are either being explored or already finished. When you pop a node, you know its left subtree is done, so it's time to process that node (the "root" part of "Left-Root-Right"), then explore its right subtree.

The Algorithm Pattern

Initialize empty stack
Set current = root

While current is not null OR stack is not empty:
    While current is not null:
        Push current onto stack
        Move current to current.left
    
    Pop node from stack
    Process node (print, collect, etc.)
    Move current to node.right

The outer loop continues until both the current node is exhausted AND there's nothing left to backtrack to in the stack.

Key Takeaway: Iterative inorder uses a stack to simulate recursion—push while going left, pop to process, then move right—achieving Left-Root-Right order without recursive calls.