Binary Tree General

Most tree problems reduce to a DFS with a clear base case and a return value that captures the needed invariant. When you build trees from traversals, the indices are the invariant.

Pattern A: Simple DFS with a base case

Use when: you need to compute depth or compare structures.

Invariant: a nil node returns the neutral base value (0 depth, true equality).

Skeleton:

func dfs(node) -> value:
    if node == nil: return base
    left = dfs(node.left)
    right = dfs(node.right)
    return combine(left, right, node)

Problems:

• maximum-depth-of-binary-tree.
• same-tree.
• invert-binary-tree.

Pattern B: Mirror comparison

Use when: you need to check symmetry.

Invariant: left subtree must mirror right subtree.

Skeleton:

func mirror(a, b):
    if a == nil and b == nil: return true
    if a == nil or b == nil: return false
    if a.val != b.val: return false
    return mirror(a.left, b.right) and mirror(a.right, b.left)

Problems:

• symmetric-tree.

Pattern C: Build tree from traversals

Use when: you have preorder+inorder or inorder+postorder.

Invariant: indices define the exact subtree range in inorder.

Skeleton (preorder + inorder):

preIndex = 0
inPos = map[value]index
func build(lo, hi):
    if lo > hi: return nil
    rootVal = preorder[preIndex]; preIndex++
    mid = inPos[rootVal]
    root.left = build(lo, mid-1)
    root.right = build(mid+1, hi)
    return root

Skeleton (inorder + postorder):

postIndex = n-1
func build(lo, hi):
    if lo > hi: return nil
    rootVal = postorder[postIndex]; postIndex--
    mid = inPos[rootVal]
    root.right = build(mid+1, hi)
    root.left = build(lo, mid-1)
    return root

Problems:

• construct-binary-tree-from-preorder-and-inorder-traversal.
• construct-binary-tree-from-inorder-and-postorder-traversal.

Pattern D: Root-to-leaf accumulation

Use when: you must check or aggregate along a root-to-leaf path.

Invariant: the running value includes the current node.

Skeleton (path sum):

func dfs(node, sum):
    if node == nil: return false
    sum += node.val
    if node.left == nil and node.right == nil:
        return sum == target
    return dfs(node.left, sum) or dfs(node.right, sum)

Skeleton (root-to-leaf numbers):

func dfs(node, val):
    if node == nil: return 0
    val = val*10 + node.val
    if leaf: return val
    return dfs(left, val) + dfs(right, val)

Problems:

• path-sum.
• sum-root-to-leaf-numbers.

Pattern E: Maximum path sum with gain

Use when: you need the maximum sum of any path (not necessarily root-to-leaf).

Invariant: each node returns the max gain from that node downwards.

Skeleton:

best = -inf
func dfs(node):
    if node == nil: return 0
    left = max(0, dfs(node.left))
    right = max(0, dfs(node.right))
    best = max(best, node.val + left + right)
    return node.val + max(left, right)

Problems:

• binary-tree-maximum-path-sum.

Pattern F: Lowest common ancestor (postorder)

Use when: you need the lowest node containing both targets.

Invariant: return the node if it is p/q or if p and q split across subtrees.

Skeleton:

func dfs(node):
    if node == nil or node == p or node == q: return node
    left = dfs(node.left)
    right = dfs(node.right)
    if left != nil and right != nil: return node
    return left if left != nil else right

Problems:

• lowest-common-ancestor-of-binary-tree.

When to use Tree DFS (checklist)

• The solution depends on values in subtrees.
• A base case can return a neutral value.
• A recursive postorder or preorder matches the need.

Common failures (checklist)

• Forgetting leaf-only conditions when required.
• Mixing up preorder vs postorder indices.
• Rebuilding index maps repeatedly instead of once.
• Neglecting nil checks in comparisons.

Problem mapping

• maximum-depth-of-binary-tree: depth via DFS.
• same-tree: structure + value comparison.
• invert-binary-tree: swap children recursively.
• symmetric-tree: mirror DFS.
• construct-binary-tree-from-preorder-and-inorder-traversal: preorder root + inorder split.
• construct-binary-tree-from-inorder-and-postorder-traversal: postorder root + inorder split.
• path-sum: root-to-leaf accumulation.
• sum-root-to-leaf-numbers: base-10 accumulation.
• binary-tree-maximum-path-sum: max gain with global best.
• lowest-common-ancestor-of-binary-tree: postorder LCA.