← Back to Blog & Downloads
Data StructuresInteractive

Binary Search Tree: Inorder Traversal

Interactive walkthrough of inorder traversal on a binary search tree, with step-by-step visualization of the recursion and call stack.

Inorder DFS
Tree Traversal

// recursive vs iterative - TypeScript implementation

Select Tree
RecursiveCall Stack Approach★ pick this for DFS
speed
// call stack (OS manages this)
current node
-
visited (inorder)
// inorder output
inorder-recursive.ts
TypeScript
// TypeScript - Recursive
interface TreeNode {
  val:   number;
  left:  TreeNode | null;
  right: TreeNode | null;
}

function inorderRecursive(
  node:   TreeNode | null,
  result: number[] = []
): number[] {

  if (node === null) return result;

  inorderRecursive(node.left,  result); // ← go LEFT first
  result.push(node.val);                // ← visit ROOT
  inorderRecursive(node.right, result); // ← then RIGHT

  return result;
}
O(n)
Time
O(h)
Space (call stack)
h=log n
balanced tree
IterativeExplicit Stack Approachgood to know
speed
stack []
empty
current node
-
// inorder output
inorder-iterative.ts
TypeScript
// TypeScript - Iterative (explicit stack)
function inorderIterative(
  root: TreeNode | null
): number[] {

  const result:  number[]    = [];
  const stack:   TreeNode[] = []; // ← we manage this!
  let   current              = root;

  while (current !== null || stack.length > 0) {

    // push LEFT nodes until we hit null
    while (current !== null) {
      stack.push(current);
      current = current.left;
    }

    current = stack.pop()!;        // ← backtrack
    result.push(current.val);      // ← visit node
    current = current.right;        // ← go RIGHT
  }

  return result;
}
O(n)
Time
O(h)
Space (explicit stack)
✓ Safe
no stack overflow
// breadth first search

BFS Level Order Traversal

Unlike DFS which goes deep before wide, BFS visits every node level by level, left to right. Uses a queue (FIFO) instead of a stack (FILO).

DFS Inorder1234567
BFS Level Order4261357
⬇
DFS Stack
LIFO, goes deep before wide
vs
➡
BFS Queue
FIFO, visits level by level
RecursiveLevel-by-Level Recursionavoid for BFS
speed
L0
4
L1
26
L2
1357
current level
-
call depth
-
// level order output
bfs-recursive.ts
TypeScript
// TypeScript - BFS Recursive
// helper: collect one level's nodes
function collectLevel(
  nodes:  TreeNode[],
  result: number[][],
  depth:  number
): void {

  if (nodes.length === 0) return; // base case

  // visit all nodes on this level
  result[depth] = nodes.map(n => n.val);

  // gather ALL children for the next level
  const nextLevel: TreeNode[] = [];
  for (const node of nodes) {
    if (node.left)  nextLevel.push(node.left);
    if (node.right) nextLevel.push(node.right);
  }

  // recurse with next level's nodes
  collectLevel(nextLevel, result, depth + 1);
}

function levelOrderRecursive(
  root: TreeNode | null
): number[][] {

  if (!root) return [];

  const result: number[][] = [];
  collectLevel([root], result, 0);
  return result;
}
⚠BFS is naturally iterative. The recursive version still passes all nodes of a level as an array; there's no single-node recursion like DFS. Stack overflow risk remains for very deep trees.
O(n)
Time
O(w)
Space (level width)
O(h)
call stack depth
IterativeQueue-Driven Approach★ pick this for BFS
speed
L0
4
L1
26
L2
1357
queue [] (FIFO)
—
current level
-
// level order output
bfs-iterative.ts
TypeScript
// TypeScript - BFS Iterative (preferred)
function levelOrderIterative(
  root: TreeNode | null
): number[][] {

  if (!root) return [];

  const result: number[][] = [];
  const queue:  TreeNode[] = [root]; // ← seed with root

  while (queue.length > 0) {

    // freeze level size BEFORE processing
    const levelSize = queue.length;
    const level:    number[] = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!; // ← FIFO dequeue
      level.push(node.val);

      if (node.left)  queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    result.push(level);
  }

  return result;
}
01
shift() not pop()
shift() = FIFO (queue front). pop() = LIFO (stack top). Using pop() here gives you DFS, the wrong algorithm entirely.
02
Freeze levelSize
Capture queue.length before the inner loop. As you enqueue children, the queue grows. The snapshot tells you where the current level ends.
03
Why iterative wins
BFS is inherently a queue algorithm. The iterative version is cleaner, safer (no call stack), and is the standard solution you'll see in interviews.
04
Enqueue order matters
Always push left before right. This preserves left-to-right reading order within each level of the output.
O(n)
Time
O(w)
Space (queue)
✓ Best
preferred approach