K AVAILABLE
OPEN TO WORK
← BACK TO KNOWLEDGE

KNOWLEDGE

Binary Tree Inorder: Iterative Stack Simulation

Simulating recursion depth-first with an explicit stack to perform Left-Root-Right tree traversals.

Updated Sep 4, 20266 min readFoundationalData Structures & Algorithms

INTERACTIVE ALGORITHM WORKBENCH

Binary Tree Inorder Traversal Visualizer

EasyTree & DFS TraversalTime O(n)Space O(h)
Binary Tree Topology
425136
Traversal State
Inorder Visited Output:
[ ]
DFS Call Stack:
Stack empty
Current NodeNode 4
Stack Depth0
Visited Count0
Traversal PhaseStarting
solution.py
1def inorder_traversal(root):
▶2    res, stack, curr = [], [], root
3    while curr or stack:
4        while curr:
5            stack.append(curr)
6            curr = curr.left
7        curr = stack.pop()
8        res.append(curr.val)
9        curr = curr.right
10    return res
Step 1 of 17
WHY THIS STEP WORKS

Inorder traversal visits Left Subtree -> Node -> Right Subtree. We use a LIFO stack to remember parent nodes while diving deep into left branches.

  1. 1Initialize stack = []
  2. 2Initialize visited = []
  3. 3Set curr = root