Depth-First Traversals

Depth-first traversal explores as far down a branch as possible before backtracking — master all three orderings in both recursive and iterative forms.

5 min read Level 2/5 #dsa#trees#dfs

What you'll learn

Produce the preorder, inorder, and postorder sequences of a given tree
Implement all three traversals recursively in JavaScript
Implement iterative inorder and preorder using an explicit stack

Depth-first search (DFS) on a tree means picking a child and following it all the way to a leaf before trying siblings. The three orderings differ only in when you process the current node relative to its children.

Preorder (root → left → right): 1, 2, 4, 5, 3
Inorder (left → root → right): 4, 2, 5, 1, 3
Postorder (left → right → root): 4, 5, 2, 3, 1

Recursive Implementation

The recursive form mirrors the definition directly:

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

function preorder(node, result = []) {
  if (!node) return result;
  result.push(node.val);          // process root first
  preorder(node.left, result);
  preorder(node.right, result);
  return result;
}

function inorder(node, result = []) {
  if (!node) return result;
  inorder(node.left, result);
  result.push(node.val);          // process root between children
  inorder(node.right, result);
  return result;
}

function postorder(node, result = []) {
  if (!node) return result;
  postorder(node.left, result);
  postorder(node.right, result);
  result.push(node.val);          // process root last
  return result;
}

Each call adds a frame to the call stack, so the implicit space complexity is O(h) where h is the height of the tree — O(log n) for balanced, O(n) worst case.

Iterative Preorder With a Stack

When recursion depth is a concern, simulate the call stack explicitly:

function preorderIterative(root) {
  if (!root) return [];
  const result = [];
  const stack = [root];

  while (stack.length) {
    const node = stack.pop();
    result.push(node.val);
    // push right first so left is processed first (LIFO)
    if (node.right) stack.push(node.right);
    if (node.left)  stack.push(node.left);
  }
  return result;
}

Iterative Inorder With a Stack

Inorder requires tracking the “current” pointer as you descend:

function inorderIterative(root) {
  const result = [];
  const stack = [];
  let curr = root;

  while (curr || stack.length) {
    // descend as far left as possible
    while (curr) {
      stack.push(curr);
      curr = curr.left;
    }
    // process the node
    curr = stack.pop();
    result.push(curr.val);
    // move to right subtree
    curr = curr.right;
  }
  return result;
}

When to Use Each Ordering

Traversal	Typical use case
Preorder	Copy a tree; serialize structure (parent before children)
Inorder	Read a BST in sorted order; expression trees
Postorder	Delete a tree; compute subtree aggregates (height, size)

Up Next

DFS goes deep first. Breadth-first search goes wide — visiting all nodes at one level before descending. That level-by-level view unlocks a different class of problems.

Breadth-First Traversal →