Tree Traversals Explained: DFS, BFS, and When to Use Each

#algorithms #computerscience #tutorial

Data Structures 1.2 — Tree Traversals (DFS & BFS)

In Part 1.1, we introduced trees and built our first binary tree. Now it’s time to answer an important question:

How do we actually move through a tree?

Tree traversals define the order in which nodes are visited. Mastering them is essential for understanding algorithms, solving interview questions, and working with real-world systems like the DOM, file systems, and search problems.

This post focuses on the two big families of traversals:

Depth-First Search (DFS): Think of DFS like walking down one hallway until it ends, then backtracking.
Breadth-First Search (BFS): Think of BFS like checking every room on the current floor before going upstairs.

Depth-First Search (DFS)

Depth-First Search explores a tree by going as deep as possible before backtracking.

DFS has three common variants:

Inorder
Preorder
Postorder

All three follow the same recursive structure — the difference is when the current node is processed.

Inorder Traversal (Left → Root → Right)

Inorder traversal first visits the left subtree, then the current node, and finally the right subtree.

This traversal is especially important for Binary Search Trees, because it returns values in sorted order.

function inorderTraversal(node) {
  if (node === null) return;

  inorderTraversal(node.left);
  console.log(node.val);
  inorderTraversal(node.right);
}

When to use inorder:

Retrieving sorted data from a BST
Validating BST structure

Preorder Traversal (Root → Left → Right)

Preorder traversal processes the current node before its children.

function preorderTraversal(node) {
  if (node === null) return;

  console.log(node.val);
  preorderTraversal(node.left);
  preorderTraversal(node.right);
}

When to use preorder:

Serializing trees
Copying tree structures
Building expression trees

Postorder Traversal (Left → Right → Root)

Postorder traversal processes the current node after both children.

function postorderTraversal(node) {
  if (node === null) return;

  postorderTraversal(node.left);
  postorderTraversal(node.right);
  console.log(node.val);
}

When to use postorder:

Deleting trees
Evaluating expressions
Bottom-up computations

Breadth-First Search (BFS)

Breadth-First Search traverses the tree level by level, from left to right.

Unlike DFS, BFS uses a queue instead of recursion.

function breadthFirstTraversal(root) {
  if (root === null) return;

  const queue = [root];

  while (queue.length > 0) {
    const current = queue.shift();
    console.log(current.val);

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

When to use BFS:

Finding the shortest path in unweighted trees
Level-order processing
Problems involving "nearest" or "minimum distance"

Both DFS and BFS visit every node once — O(n) time.

The key difference is space:

DFS uses space proportional to the tree height (call stack)
BFS uses space proportional to the widest level (queue)

DFS vs BFS — How to Choose?

Here’s a simple mental model:

Use DFS when:
- You want to explore deep paths
- You’re working recursively
- The tree depth is manageable
Use BFS when:
- You need the shortest path
- You care about levels
- You want the closest node