Tree traversals (DFS and BFS) — Data structures

Traversing a tree

A tree stores data in a hierarchy of nodes, but we often need to visit all of them: to search, sum, print, or transform. There are two classic strategies, and the difference is the order in which the nodes are visited.

Imagine you are exploring a building of connected rooms. You can go down a hallway all the way to the end before coming back (depth), or check first all the doors on your floor before going down to the next one (breadth).

DFS — Depth-First Search

DFS goes down a branch all the way to the bottom before backtracking and trying the next one. It is expressed very naturally with recursion: you visit the node and then call yourself on each child.

function dfs(node, visit) {
  visit(node.value);
  for (const child of node.children) {
    dfs(child, visit);
  }
}

Recursion uses the call stack under the hood: each call waits for its children's calls to finish. That is why DFS and "stack" go hand in hand.

BFS — Breadth-First Search

BFS visits the nodes level by level: first the root, then all its children, then the grandchildren... To achieve this, a queue (FIFO) is used: we put in the root, and while the queue is not empty, we take out a node, visit it, and enqueue its children at the end.

function bfs(root, visit) {
  const queue = [root];
  while (queue.length > 0) {
    const node = queue.shift(); // takes out the first one (FIFO)
    visit(node.value);
    for (const child of node.children) {
      queue.push(child); // the children wait their turn at the end
    }
  }
}

Which one do I choose?

DFS: when you want to explore complete paths (find a route, sum a whole branch). Simpler to write with recursion.
BFS: when closeness to the root matters (the shortest path in number of steps, processing level by level).

Examples

Recursive DFS: visits complete branches

const root = { value: "A", children: [
  { value: "B", children: [{ value: "D", children: [] }, { value: "E", children: [] }] },
  { value: "C", children: [] },
]};
const order = [];
function dfs(node) {
  order.push(node.value);
  for (const child of node.children) dfs(child);
}
dfs(root);
console.log(order.join(" -> ")); // A -> B -> D -> E -> C

BFS with a queue: visits level by level

const root = { value: "A", children: [
  { value: "B", children: [{ value: "D", children: [] }, { value: "E", children: [] }] },
  { value: "C", children: [] },
]};
const order = [];
const queue = [root];
while (queue.length > 0) {
  const node = queue.shift();
  order.push(node.value);
  for (const child of node.children) queue.push(child);
}
console.log(order.join(" -> ")); // A -> B -> C -> D -> E