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
At root 3: recurse left and right; each call returns a hit or None.
Live template
Line 1 active
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).
- For each node, compute best downward gain:
node.val + max(0, left_gain, right_gain). - Candidate path through this node:
node.val + max(0,left) + max(0,right), update global best. - Return only the single-arm gain to the parent (paths cannot fork upward).
- 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.