Trees & Graphs — Traversal, BFS, DFS & Common Patterns

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 (used to copy/serialize trees)
function preorder(root: TreeNode | null): number[] {
  if (!root) return [];
  return [root.val, ...preorder(root.left), ...preorder(root.right)];
}

// Postorder — Left → Right → Root (used to delete trees, evaluate expressions)
function postorder(root: TreeNode | null): number[] {
  if (!root) return [];
  return [...postorder(root.left), ...postorder(root.right), root.val];
}

// Iterative inorder (common in interviews)
function inorderIterative(root: TreeNode | null): number[] {
  const result: number[] = [];
  const stack: TreeNode[] = [];
  let curr: TreeNode | null = root;

  while (curr || stack.length > 0) {
    while (curr) { stack.push(curr); curr = curr.left; }
    curr = stack.pop()!;
    result.push(curr.val);
    curr = curr.right;
  }

  return result;
}

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 level: number[] = [];

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

    result.push(level);
  }

  return result;
}
// Time: O(n) | Space: O(n)

function maxDepth(root: TreeNode | null): number {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
// Time: O(n) | Space: O(h) where h = height

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);
}
// Time: O(n) | Space: O(h)

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 on different sides — this is LCA
  return left ?? right;             // one side found both
}
// Time: O(n) | Space: O(h)

function maxPathSum(root: TreeNode | null): number {
  let globalMax = -Infinity;

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

    const left  = Math.max(0, dfs(node.left));   // ignore negative paths
    const right = Math.max(0, dfs(node.right));

    // This node as the "turn" point — include both children
    globalMax = Math.max(globalMax, node.val + left + right);

    // Return the max single path extending from this node
    return node.val + Math.max(left, right);
  }

  dfs(root);
  return globalMax;
}
// Time: O(n) | Space: O(h)

function serialize(root: TreeNode | null): string {
  if (!root) return 'null';
  return `${root.val},${serialize(root.left)},${serialize(root.right)}`;
}

function deserialize(data: string): TreeNode | null {
  const nodes = data.split(',');
  let i = 0;

  function build(): TreeNode | null {
    if (nodes[i] === 'null') { i++; return null; }
    const node = new TreeNode(Number(nodes[i++]));
    node.left  = build();
    node.right = build();
    return node;
  }

  return build();
}

// Adjacency list representation (most common in interviews)
type Graph = Map<number, number[]>;

const graph: Graph = new Map([
  [0, [1, 2]],
  [1, [0, 3]],
  [2, [0, 4]],
  [3, [1]],
  [4, [2]],
]);

function dfs(graph: Graph, start: number): number[] {
  const visited = new Set<number>();
  const result: number[] = [];

  function explore(node: number): void {
    if (visited.has(node)) return;
    visited.add(node);
    result.push(node);
    for (const neighbor of graph.get(node) ?? []) {
      explore(neighbor);
    }
  }

  explore(start);
  return result;
}
// Time: O(V + E) | Space: O(V)

function bfs(graph: Graph, start: number): number[] {
  const visited = new Set<number>([start]);
  const queue   = [start];
  const result: number[] = [];

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

    for (const neighbor of graph.get(node) ?? []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }

  return result;
}
// Time: O(V + E) | Space: O(V)

function numIslands(grid: string[][]): number {
  const rows = grid.length, cols = grid[0].length;
  let count = 0;

  function sink(r: number, c: number): void {
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== '1') return;
    grid[r][c] = '0';  // mark visited by "sinking" the land
    sink(r + 1, c); sink(r - 1, c);
    sink(r, c + 1); sink(r, c - 1);
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        count++;
        sink(r, c);
      }
    }
  }

  return count;
}
// Time: O(m × n) | Space: O(m × n) call stack

function shortestPath(grid: number[][], start: [number,number], end: [number,number]): number {
  const rows = grid.length, cols = grid[0].length;
  const visited = Array.from({ length: rows }, () => new Array(cols).fill(false));
  const queue: [[number, number], number][] = [[start, 0]];
  const dirs = [[0,1],[0,-1],[1,0],[-1,0]];

  visited[start[0]][start[1]] = true;

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

    if (r === end[0] && c === end[1]) return dist;

    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
          && !visited[nr][nc] && grid[nr][nc] === 0) {
        visited[nr][nc] = true;
        queue.push([[nr, nc], dist + 1]);
      }
    }
  }

  return -1;  // no path found
}
// Time: O(m × n) | Space: O(m × n)

function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  const graph: number[][] = Array.from({ length: numCourses }, () => []);
  for (const [course, prereq] of prerequisites) {
    graph[prereq].push(course);
  }

  // 0 = unvisited, 1 = in-progress (cycle!), 2 = done
  const state = new Array(numCourses).fill(0);

  function hasCycle(node: number): boolean {
    if (state[node] === 1) return true;   // back edge — cycle!
    if (state[node] === 2) return false;  // already fully processed

    state[node] = 1;
    for (const neighbor of graph[node]) {
      if (hasCycle(neighbor)) return true;
    }
    state[node] = 2;
    return false;
  }

  for (let i = 0; i < numCourses; i++) {
    if (hasCycle(i)) return false;
  }

  return true;
}
// Time: O(V + E) | Space: O(V + E)

Tree problem → try DFS recursion first
  "Max/min of subtree"     → postorder (compute children first)
  "Path from root"         → preorder (track running state)
  "Validate structure"     → pass bounds down as parameters
  "Level-by-level"         → BFS with queue

Graph problem → identify if BFS or DFS
  "Shortest path"          → BFS (unweighted) / Dijkstra (weighted)
  "Is connected?"          → DFS or Union-Find
  "Cycle detection"        → DFS with in-progress set
  "Topological order"      → DFS postorder or Kahn's BFS
  "Grid traversal"         → DFS (flood-fill, islands) / BFS (shortest path)

Always:
  Track visited to avoid infinite loops
  Handle null/empty base case first
  For graphs: visited set is mandatory