Metis

Field note / fundamentals

publishedupdated 2026-05-04#algorithms#trees#graphs#dynamic-programming#dfs

Algorithms Practice: Trees, Graphs, and Dynamic Programming

A compact study map for traversal, path problems, cycle detection, and the dynamic-programming mindset.

TL;DR

  • Trees and graphs are traversal problems first and data-structure problems second.
  • DFS and BFS solve different classes of questions, so I pick based on the shape of the answer I need.
  • Dynamic programming gets easier when I define the state, recurrence, and base cases clearly.
  • I practice these patterns by turning big problems into repeatable subproblems.

Context

This is the part of interview prep where pattern recognition matters most. I do not try to memorize dozens of solutions. I try to identify traversal shape, state definition, and whether overlapping subproblems exist.

The Approach

This map is how I think about it:

I first identify traversal structure, then check whether repeated subproblems justify dynamic programming.

Tree DFS example:

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

Classic DP example:

function climbStairs(steps: number): number {
  if (steps <= 2) return steps

  let prev2 = 1
  let prev1 = 2

  for (let current = 3; current <= steps; current += 1) {
    const next = prev1 + prev2
    prev2 = prev1
    prev1 = next
  }

  return prev1
}

Trade-offs

  • DFS is simple and expressive, but recursion depth can become a real constraint.
  • BFS is often the cleanest way to get shortest path in an unweighted graph, but it uses more memory on wide frontiers.
  • Dynamic programming is powerful, but it is easy to overcomplicate if the state definition is not minimal.

References