Trees & Graphs

Tree traversal

DFS goes deep before going wide. BFS goes wide before going deep. The three DFS orderings differ only in when you process the current node relative to its children.

Graph BFS — shortest path

Unlike a tree, a graph can have cycles. BFS explores level by level and finds the shortest path in an unweighted graph. A visited set prevents revisiting nodes.

Templates

Tree DFS — recursive

function dfs(node: TreeNode | null) {
  if (!node) return

  // pre-order: process here
  dfs(node.left)
  // in-order: process here
  dfs(node.right)
  // post-order: process here
}

Tree BFS — iterative with queue

function bfs(root: TreeNode) {
  const queue = [root]

  while (queue.length) {
    const node = queue.shift()!
    // process node
    if (node.left) queue.push(node.left)
    if (node.right) queue.push(node.right)
  }
}

Graph BFS — with visited set

function bfs(graph: number[][], start: number) {
  const visited = new Set([start])
  const queue = [start]

  while (queue.length) {
    const node = queue.shift()!
    // process node
    for (const nb of graph[node])
      if (!visited.has(nb)) {
        visited.add(nb)
        queue.push(nb)
      }
  }
}