Trees, Graphs & BFS/DFS

TL;DR

• BFS (Breadth-First): Level-by-level. Uses queue. Shortest path in unweighted graphs.
• DFS (Depth-First): Go deep first. Uses stack/recursion. Detect cycles, topological sort.
• Binary Trees: Inorder (sorted), Preorder (serialize), Postorder (delete).
• Graphs: Adjacency list representation. Watch for visited tracking to avoid infinite loops.

Step 1: Binary Tree Traversals

Trees are everywhere in computing — file systems, DOM, database indexes, JSON parsing, org charts. Tree traversals were formalized because you constantly need to visit every node in a specific order: inorder gives you sorted data from a BST, preorder lets you serialize/copy a tree, and postorder is how you safely delete nodes (children before parent). Level-order (BFS) is how search engines crawl links and how you'd print a family tree generation by generation. Understanding traversals is the foundation for every tree problem you'll encounter.

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

// Inorder: Left → Root → Right (gives sorted order for BST)
function inorder(root: TreeNode | null): number[] {
  if (!root) return [];
  return [...inorder(root.left), root.val, ...inorder(root.right)];
}

// Preorder: Root → Left → Right (good for copying/serializing)
function preorder(root: TreeNode | null): number[] {
  if (!root) return [];
  return [root.val, ...preorder(root.left), ...preorder(root.right)];
}

// Postorder: Left → Right → Root (good for deletion)
function postorder(root: TreeNode | null): number[] {
  if (!root) return [];
  return [...postorder(root.left), ...postorder(root.right), root.val];
}

// Level-order (BFS) — uses queue
function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return [];
  const result: number[][] = [];
  const queue: TreeNode[] = [root];

  while (queue.length > 0) {
    const levelSize = queue.length;
    const currentLevel: number[] = [];

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      currentLevel.push(node.val);
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }

    result.push(currentLevel);
  }

  return result;
}

Step 2: Common Tree Problems

These problems appear so frequently in interviews because trees test recursive thinking — can you break a problem into "solve for left subtree + solve for right subtree + combine"? Companies love them because they reveal how you think about base cases, null handling, and building solutions bottom-up. Max depth, LCA, and BST validation are among the most-asked tree questions at FAANG companies, and they each teach a different recursive pattern you'll reuse across dozens of other problems.

Max Depth

function maxDepth(root: TreeNode | null): number {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Validate BST

function isValidBST(
  root: TreeNode | null,
  min = -Infinity,
  max = Infinity
): boolean {
  if (!root) return true;
  if (root.val <= min || root.val >= max) return false;
  return (
    isValidBST(root.left, min, root.val) &&
    isValidBST(root.right, root.val, max)
  );
}

Lowest Common Ancestor (LCA)

function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode,
  q: TreeNode
): TreeNode | null {
  if (!root || root === p || root === q) return root;

  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);

  if (left && right) return root;  // p and q are on different sides
  return left ?? right;            // Both on same side
}

Invert Binary Tree

function invertTree(root: TreeNode | null): TreeNode | null {
  if (!root) return null;
  [root.left, root.right] = [invertTree(root.right), invertTree(root.left)];
  return root;
}

Same Tree

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
  if (!p && !q) return true;
  if (!p || !q) return false;
  return (
    p.val === q.val &&
    isSameTree(p.left, q.left) &&
    isSameTree(p.right, q.right)
  );
}

Step 3: Graph Representation

Graphs model relationships that trees can't — social networks, road maps, dependency systems, the internet itself. The adjacency list representation became standard because most real-world graphs are sparse (each node connects to few others relative to total nodes), and adjacency lists use O(V + E) space vs O(V²) for a matrix. Knowing how to build a graph from an edge list is step zero for every graph algorithm, and interviewers expect you to do it from memory.

// Adjacency List (most common)
// Graph: 0 → [1, 2], 1 → [2], 2 → [3]
const graph = new Map<number, number[]>();
graph.set(0, [1, 2]);
graph.set(1, [2]);
graph.set(2, [3]);
graph.set(3, []);

// Build from edge list
function buildGraph(n: number, edges: [number, number][]): Map<number, number[]> {
  const graph = new Map<number, number[]>();
  for (let i = 0; i < n; i++) graph.set(i, []);

  for (const [u, v] of edges) {
    graph.get(u)!.push(v);
    graph.get(v)!.push(u); // Remove for directed graph
  }

  return graph;
}

Step 4: BFS — Breadth-First Search

BFS was invented to find shortest paths in unweighted graphs. It explores level-by-level, guaranteeing that the first time you reach a node, you've taken the minimum number of steps to get there. This is why GPS navigation, social media "degrees of separation", and network packet routing all use BFS at their core. In coding interviews, any time you see "minimum moves", "shortest path", or "nearest X" in an unweighted context, BFS is your answer. It's also the basis for level-order tree traversal and multi-source spreading problems (like rotting oranges).

// BFS: shortest path in unweighted graph
function bfs(graph: Map<number, number[]>, start: number, target: number): number {
  const visited = new Set<number>([start]);
  const queue: [number, number][] = [[start, 0]]; // [node, distance]

  while (queue.length > 0) {
    const [node, dist] = queue.shift()!;

    if (node === target) return dist;

    for (const neighbor of graph.get(node) || []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, dist + 1]);
      }
    }
  }

  return -1; // Not reachable
}

// BFS on grid: shortest path in maze
function shortestPath(grid: number[][]): number {
  const rows = grid.length, cols = grid[0].length;
  if (grid[0][0] === 1 || grid[rows - 1][cols - 1] === 1) return -1;

  const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
  const queue: [number, number, number][] = [[0, 0, 1]]; // [row, col, distance]
  const visited = new Set<string>(['0,0']);

  while (queue.length > 0) {
    const [row, col, dist] = queue.shift()!;

    if (row === rows - 1 && col === cols - 1) return dist;

    for (const [dr, dc] of directions) {
      const newRow = row + dr, newCol = col + dc;
      const key = `${newRow},${newCol}`;

      if (
        newRow >= 0 && newRow < rows &&
        newCol >= 0 && newCol < cols &&
        grid[newRow][newCol] === 0 &&
        !visited.has(key)
      ) {
        visited.add(key);
        queue.push([newRow, newCol, dist + 1]);
      }
    }
  }

  return -1;
}

Step 5: DFS — Depth-First Search

DFS was the natural counterpart to BFS — instead of exploring all neighbors first, you dive as deep as possible before backtracking. It uses less memory than BFS for deep graphs (stack vs queue of all nodes at a level), and it naturally detects cycles and finds connected components. DFS is the backbone of topological sorting, solving mazes, finding articulation points, and any problem where you need to explore all possible paths. The "number of islands" problem (counting connected components on a grid) is one of the most frequently asked interview questions worldwide.

// DFS: detect cycle in directed graph
function hasCycle(graph: Map<number, number[]>, n: number): boolean {
  const visited = new Set<number>();
  const inStack = new Set<number>(); // Current DFS path

  function dfs(node: number): boolean {
    visited.add(node);
    inStack.add(node);

    for (const neighbor of graph.get(node) || []) {
      if (inStack.has(neighbor)) return true;  // Back edge = cycle!
      if (!visited.has(neighbor) && dfs(neighbor)) return true;
    }

    inStack.delete(node); // Backtrack
    return false;
  }

  for (let i = 0; i < n; i++) {
    if (!visited.has(i) && dfs(i)) return true;
  }
  return false;
}

// DFS: Number of islands (connected components on grid)
function numIslands(grid: string[][]): number {
  const rows = grid.length, cols = grid[0].length;
  let count = 0;

  function dfs(r: number, c: number) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] === '0') return;
    grid[r][c] = '0'; // Mark visited
    dfs(r + 1, c);
    dfs(r - 1, c);
    dfs(r, c + 1);
    dfs(r, c - 1);
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        count++;
        dfs(r, c); // Sink the entire island
      }
    }
  }

  return count;
}

Step 6: Topological Sort

Topological sort exists because real-world systems have dependencies — you can't compile module B before module A if B imports A, you can't take Advanced Math before Calculus, you can't deploy service X before its database is ready. Kahn's algorithm (BFS-based) was invented to linearize these dependency graphs into a valid execution order. It also doubles as a cycle detector: if you can't topologically sort all nodes, there's a circular dependency. Build tools (webpack, turborepo), package managers (npm), task schedulers, and course prerequisite systems all use this algorithm.

// Topological sort: ordering where A comes before B if A → B
// Used for: build systems, course prerequisites, task scheduling

function topologicalSort(n: number, edges: [number, number][]): number[] {
  const graph = new Map<number, number[]>();
  const inDegree = new Array(n).fill(0);

  for (let i = 0; i < n; i++) graph.set(i, []);
  for (const [from, to] of edges) {
    graph.get(from)!.push(to);
    inDegree[to]++;
  }

  // Start with nodes that have no prerequisites
  const queue: number[] = [];
  for (let i = 0; i < n; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }

  const result: number[] = [];
  while (queue.length > 0) {
    const node = queue.shift()!;
    result.push(node);

    for (const neighbor of graph.get(node)!) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }

  // If result.length < n, there's a cycle (impossible to sort)
  return result.length === n ? result : [];
}

// Course Schedule — can you finish all courses?
function canFinish(numCourses: number, prerequisites: [number, number][]): boolean {
  return topologicalSort(numCourses, prerequisites).length === numCourses;
}

Step 7: Dijkstra's Algorithm (Weighted Shortest Path)

Dijkstra's algorithm (1956) solved the problem BFS can't handle: finding shortest paths when edges have different weights/costs. A GPS finding the fastest route between cities can't just count road segments — it needs to sum travel times. Dijkstra's greedily picks the closest unvisited node and relaxes its neighbors, giving O((V+E) log V) with a priority queue. It's used in network routing protocols (OSPF), game pathfinding, flight booking systems, and any weighted graph where you need the cheapest/fastest path.

// Shortest path in weighted graph (non-negative weights)
function dijkstra(
  graph: Map<number, [number, number][]>, // node → [[neighbor, weight]]
  start: number,
  n: number
): number[] {
  const dist = new Array(n).fill(Infinity);
  dist[start] = 0;

  // Min-heap: [distance, node]
  const pq: [number, number][] = [[0, start]];
  const visited = new Set<number>();

  while (pq.length > 0) {
    // Sort to simulate priority queue (use proper heap in production)
    pq.sort((a, b) => a[0] - b[0]);
    const [d, node] = pq.shift()!;

    if (visited.has(node)) continue;
    visited.add(node);

    for (const [neighbor, weight] of graph.get(node) || []) {
      const newDist = d + weight;
      if (newDist < dist[neighbor]) {
        dist[neighbor] = newDist;
        pq.push([newDist, neighbor]);
      }
    }
  }

  return dist; // dist[i] = shortest path from start to i
}

BFS vs DFS Decision

Interview Questions

1. BFS vs DFS — when to use which?

   • BFS: shortest path in unweighted graphs, level-order traversal, minimum steps. DFS: cycle detection, topological sort, path existence, exhaustive search, less memory for deep/narrow graphs.

2. How do you detect a cycle in a graph?

   • Directed graph: DFS with "currently in stack" tracking. If you visit a node already in the current path, it's a cycle. Undirected: if you visit an already-visited node that isn't the parent.

3. What's topological sort used for?

   • Ordering tasks with dependencies (course scheduling, build systems, package installation). Only works on DAGs (Directed Acyclic Graphs). If a cycle exists, topological sort is impossible.

4. Time/space complexity of BFS and DFS?

   • Both: O(V + E) time where V = vertices, E = edges. BFS space: O(V) for the queue (worst case: all nodes in one level). DFS space: O(V) for recursion stack (worst case: linear graph).