Trees

Tree Paths & LCA

Path sums, diameters and lowest common ancestors by returning information up the tree.

Hard, about 90 minutes to practise.

1Understand

The idea

Let each recursive call return information up to its parent, such as the best path that ends at this node, while updating a global answer with paths that turn at this node (they use both children). The lowest common ancestor is the first node where the two targets are found in different subtrees.

Intuition

Let each recursive call return information up to its parent, for example the best path sum that ends at this node, while a global answer tracks paths that turn at this node and use both children.

LCA is the first node where the two targets sit in different subtrees (or one target is an ancestor of the other). One DFS can return a status: found p, found q, or found both (this node is the LCA).

Path problems and LCA share the "return info upward, update answer at the combine point" shape.

What you will be able to do

  • Separate "best through node" from "best going up"
  • Use a nonlocal or list for the global best

When to use it

  • Path between two nodes
  • Maximum path sum or diameter
  • Lowest common ancestor

2See it

Walkthrough

Lowest common ancestor

Nodes [3, 5, 1, 6, 2], p=6, q=2, recurse; first node seeing both sides.

1 / 5

i
3
5
1
6
2
01234
i → index 0

At root 3: recurse left and right; each call returns a hit or None.

left, right = lca(node.left), lca(node.right)

Live template

Line 1 active

1def dfs(node):
2 if not node: return 0
3 l, r = dfs(node.left), dfs(node.right)
4 best[0] = max(best[0], l + r + node.val) # path through node
5 return node.val + max(l, r, 0) # path going up

Complexity: time O(n), space O(h)

One DFS is O(n) time and O(h) space. Separate searches for paths to p and q use extra memory for the paths. Returning tuples of states keeps a single traversal.

Read the walkthrough as text

Binary tree max path sum (idea). Node values [-10,9,20,null,null,15,7] (LeetCode shape).

  1. For each node, compute best downward gain: node.val + max(0, left_gain, right_gain).
  2. Candidate path through this node: node.val + max(0,left) + max(0,right), update global best.
  3. Return only the single-arm gain to the parent (paths cannot fork upward).
  4. Best path uses 15-20-7.

For LCA of p and q, recurse; if both sides return non-null, current node is LCA; else bubble up the non-null side.

3Recognise it

Kinds of problems (5)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Root-to-leaf path sum

    Example. Does any root-to-leaf path equal target sum?

    How. DFS subtract node.val; at a leaf compare remaining sum to zero.

  • Diameter

    Example. Longest path between any two nodes (edges count).

    How. Per node, best through-node = leftDepth + rightDepth; return max single branch up.

  • Maximum path sum

    Example. Largest sum of any path (nodes may be negative).

    How. Same split: global best uses left+right+val; upward return is val + max(child, 0).

  • Lowest common ancestor

    Example. LCA of two nodes in a binary tree.

    How. Post-order: if p or q in subtree, bubble up; first node with both sides wins.

  • Count paths with a target sum (prefix sums)

    Example. Count downward paths whose node sum equals target.

    How. DFS with map prefixSum→count; at each node add count of (cur−target) seen on path.

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • Through vs up confused

    Why it happens. Returning the combined branch sum upward looks like the “path through” answer.

    How it fails. Max path sum returns left+right+val to parent, parent double-counts branches and inflates totals.

    Fix. Globally track through-node best; upward return is single-branch max(child, 0) + val.

  • Negative branches

    Why it happens. Negative subtree sums still get added because “a path is a path”.

    How it fails. Child sum −100 still added, best upward path shrinks when dropping the branch would be better.

    Fix. Treat negative contributions as 0 when extending a single branch upward (max(l, r, 0)).

  • Leaf misidentified

    Why it happens. A node with one child still “ends” a path in your head.

    How it fails. Path sum target matched at an internal node with only one child, counted when problem wants leaves.

    Fix. Check leaf with `not left and not right` before accepting path-sum answers.

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons