Tree DFS

How to think about it

Write a function f(node) that returns what the parent needs (height, is-BST flag, min/max, best path through node). Solve left and right first, then combine. Sometimes also update a global best.

The interactive mental model draws the actual tree (edges + nodes), not a flat list: watch values and badges (heights, LCA markers) flow up the structure.

Template shapes

Shape	Core move	Notes
Return height	1+max(L,R)	Depth, balance
Return multi-field	struct of flags	BST / diameter
Pass bounds	low < val < high	Validate BST

Complexity baseline

O(n) time visits each node once; space O(h) recursion stack.

From template to problem

1. Specify f(node)’s return type in one sentence.
2. Base case for null.
3. Recurse left/right; combine; optionally update global answer.
4. Return the value the parent requires.

/** Tree DFS template: max depth. */
export class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val; this.left = left; this.right = right;
  }
}
export function maxDepth(root: TreeNode | null): number {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

/** Tree DFS template: max depth. */
export class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val; this.left = left; this.right = right;
  }
}
export function maxDepth(root: TreeNode | null): number {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}