169: DSA - Trees, Heaps, and Binary Search

Learning outcomes

traverse trees iteratively and recursively;
maintain heap and search invariants;
choose a binary-search boundary convention.

Practice

Implement preorder, level-order traversal, top-k values with a heap, and binary search for the first valid boundary. Test a missing value, duplicate values, skewed trees, and a one-element range.

Lesson and worked examples

For a tree, preorder visits node-left-right and level order uses a queue. On root 4 with children 2 and 6, level order is [4, 2, 6]; an iterative traversal avoids call-stack growth on a skewed tree. A min-heap of size k solves top-k: insert each value, and when size exceeds k, remove the smallest. This is O(n log k), better than sorting when k is small.

Use a half-open binary-search interval [low, high) for the first index satisfying a monotonic predicate. If predicate(mid) is true, keep mid with high = mid; otherwise set low = mid + 1. Example: in [1, 2, 2, 5], first value >= 2 is index 1. Return low == n when all values fail, if that is the API contract.

Tests and rubric

Test null and one-node trees, skewed trees, duplicate keys, empty and full heaps, k = 0, k > n, missing values, all-false/all-true predicates, first and last boundaries, and a one-element range. Score 3 points each for traversal correctness, heap invariant/complexity, explicit interval convention, recursion-risk discussion, and tests. Explain whether a BST property is required; ordinary tree traversal does not have one.

Checkpoint

Explain why binary search needs a monotonic predicate and why recursion depth can be a runtime concern.

Boundary convention

Choose one interval convention before coding. With [low, high), continue while low < high, inspect mid = low + Math.floor((high - low) / 2), and move high = mid when the predicate is true. Test all-false, all-true, one-element, and duplicate-value inputs. The correctness argument is the maintained search interval, not the loop shape alone.

Matrix and grid problems

A matrix problem usually has two separate concerns: staying inside row and column bounds, and deciding whether a cell is visited. For a rectangular matrix, use rows = grid.length and columns = grid[0]?.length ?? 0; never assume the number of rows equals the number of columns.

js
function floodFill(grid, startRow, startColumn) {
  const rows = grid.length;
  const columns = grid[0]?.length ?? 0;
  if (!rows || !columns) return grid;
  const target = grid[startRow]?.[startColumn];
  if (target === undefined) return grid;
  const queue = [[startRow, startColumn]];
  const seen = new Set([`${startRow},${startColumn}`]);
  const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];

  for (let index = 0; index < queue.length; index += 1) {
    const [row, column] = queue[index];
    for (const [rowStep, columnStep] of directions) {
      const nextRow = row + rowStep;
      const nextColumn = column + columnStep;
      const key = `${nextRow},${nextColumn}`;
      if (nextRow >= 0 && nextRow < rows && nextColumn >= 0 && nextColumn < columns
        && grid[nextRow][nextColumn] === target && !seen.has(key)) {
        seen.add(key);
        queue.push([nextRow, nextColumn]);
      }
    }
  }
  return seen;
}

The invariant is that every queued cell is in bounds, matches the target, and is queued once. Spiral traversal uses shrinking top, right, bottom, and left boundaries; rotation can be decomposed into transpose followed by reversing each row. For a grid with R * C cells, traversal is O(RC) time and O(RC) space in the worst case.

Matrix practice

Implement spiral traversal, in-place 90-degree rotation for a square matrix, and shortest-path distance through blocked cells. Test an empty matrix, one cell, one row, one column, a rectangular matrix, a ragged matrix if it is allowed, repeated values, and a start equal to the target. Explain why a ragged matrix needs a different bounds check.