DSA Roadmap/Trees

Advanced Tree Patterns (LCA, Diameter, Paths)

The single recursive template — ask my children, combine, report to my parent — that solves LCA, diameter, and most of the 'hard'-rated tree problems you'll face.

!!4/5Theory: 2h4 problems

The one template that solves most "hard" tree problems

Nearly every tree problem rated Medium-or-above on LeetCode is a variation of the same recursive shape:

Define a function that, given a node, computes and returns some information about the subtree rooted there — using the information its children already returned — and along the way, possibly updates a running "best answer seen so far" that lives outside any single subtree's return value.

This has two moving parts that are worth naming explicitly, because conflating them is the most common source of confusion when these problems get hard:

  1. What a node returns to its parent — this must be something the parent can actually use to keep computing (e.g., "the height of my subtree," "the longest downward path starting at me"). It is necessarily a single-sided piece of information, because the parent only knows it has a left child and a right child — it doesn't know or care what happened two levels down.
  2. The actual answer to the problem — which often needs to consider a path or value that "bends" at some node (uses both its left and right subtree simultaneously), and therefore can never be correctly expressed as a value returned up to a grandparent. This is almost always tracked as a side variable (nonlocal in Python, an instance attribute in Java/C++) that gets updated, never returned, at each node.
def solve(root): best = float("-inf") # tracks the true, possibly-"bent" answer def dfs(node): nonlocal best if node is None: return 0 # neutral value for "no subtree here" left = dfs(node.left) # single-sided info from left subtree right = dfs(node.right) # single-sided info from right subtree # the "bent" candidate, using BOTH sides — only valid to consider HERE best = max(best, combine_both_sides(node, left, right)) # the single-sided value THIS node reports up to its own parent return combine_one_side(node, max(left, right)) dfs(root) return best

This shape underlies diameter, binary tree maximum path sum, and a large fraction of "compute X over all paths/subtrees" problems in this subtopic's problem list — the differences between them are almost entirely in what combine_both_sides and combine_one_side compute, not in the recursive skeleton itself. It's worth internalizing this template as a single unit rather than memorizing each problem separately.

Lowest Common Ancestor: general tree vs. BST

General binary tree — no ordering to exploit. With no structural shortcut available, the only option is to search both subtrees and reason about what comes back:

def lca_general(node, p, q): if node is None or node is p or node is q: return node left = lca_general(node.left, p, q) right = lca_general(node.right, p, q) if left and right: # p and q were found on different sides — node is the split point return node return left if left else right # both were found on the same side, or only one was found

This is a direct instance of the "ask children, combine" template: each call returns "the LCA candidate found so far in this subtree" — which happens to be p or q itself if that's all that's been found, or the true LCA once both targets have been located on opposite sides.

BST — the ordering is the shortcut. Because every node's value tells you which subtree p and q must be in relative to it, you never need to search both sides:

def lca_bst(node, p_val, q_val): while node: if p_val < node.val and q_val < node.val: node = node.left elif p_val > node.val and q_val > node.val: node = node.right else: return node # p and q split here (or node.val equals one of them) return None
VariantTimeSpaceWhy
General binary treeO(n)O(h) recursion stackMust visit every node in the worst case; no ordering to prune with
BSTO(h)O(1) iterative / O(h) recursiveValue comparisons let you discard an entire subtree at each step, exactly like BST search

If you ever catch yourself writing the O(n) general-tree solution for a problem that explicitly says BST, that's a signal you haven't connected this subtopic back to the BST invariant — the BST version is a direct application of the search logic from that subtopic, not a new algorithm.

Diameter-shaped problems: combining two single-sided values into a "bent" answer

"Diameter" (the longest path between any two nodes) is the canonical example of the combine_both_sides/combine_one_side split: at each node, the candidate diameter through this node is left_height + right_height (both sides, because the path can bend here), while the value reported up to the parent must be 1 + max(left_height, right_height) (only one side, since a path can't fork twice). If you return the two-sided sum to the parent by mistake, the algorithm silently produces wrong answers on any tree where the true longest path doesn't pass through the root — a bug that's easy to miss because it still produces a number, just the wrong one. This same shape reappears, with different combine functions, for binary tree maximum path sum and several tree-DP-flavored problems in this list.

Root-to-leaf and path-sum patterns

Path problems come in a few distinct flavors that are easy to conflate:

VariantMust start at root?Must end at a leaf?Can it "bend" at a node?
Root-to-leaf path sumYesYesNo — it's a single downward path by definition
Any-node-to-leafNoYesNo
Any-node-to-any-node ("maximum path sum" style)NoNoYes — this is exactly the diameter-shaped combine logic above

The negative-values gotcha. A very common instinct on sum-based problems is to prune early — "stop descending once the running sum exceeds the target." That's a valid optimization only when all values are guaranteed non-negative (sums are monotonically non-decreasing as you go deeper). The moment negative values are allowed, an exceeded sum can come back down later, so early-exit-on-exceeded-sum silently produces wrong answers. Always check the constraints before applying that kind of pruning — and note that both Binary Tree Maximum Path Sum and Sum Root to Leaf Numbers in this subtopic's problem list are exactly the kind of question where getting this wrong is easy to miss on your own.

Returning multiple pieces of information from one pass

Sometimes a node needs to report more than one value upward — e.g., "the height of my subtree" and "whether my subtree is balanced" simultaneously, so the parent can check balance without a second full traversal. Two idiomatic ways to do this:

# Option 1: tuple / small return type def dfs(node): if node is None: return (0, True) # (height, is_balanced) left_h, left_ok = dfs(node.left) right_h, right_ok = dfs(node.right) balanced = left_ok and right_ok and abs(left_h - right_h) <= 1 return (1 + max(left_h, right_h), balanced) # Option 2: mutable/nonlocal state for values that don't need to flow back "up" the call chain def dfs_with_side_state(node, counter): if node is None: return counter["visited"] += 1 # e.g. a running total across the whole tree dfs_with_side_state(node.left, counter) dfs_with_side_state(node.right, counter)

Prefer the tuple/return-value approach whenever the information genuinely needs to flow back up to be combined by an ancestor (as in the balanced-height example — this also avoids the O(n²) trap of computing height freshly at every node). Reach for a side variable only for the "bent"/global-answer case described in the very first template, where the value being tracked isn't something any single ancestor needs returned to it — it just needs to end up correct by the time the whole traversal finishes.

Complexity

Every pattern in this subtopic visits each node a constant number of times, so time complexity is uniformly O(n). Space is O(h) for the recursion stack — O(log n) on a balanced tree, O(n) on a skewed one, per the same recursion-depth reasoning introduced in Big-O & Complexity Analysis and repeated throughout this topic.

Common pitfalls

  • Returning the "bent" (both-sides) value to the parent instead of the single-sided one. This is the single most common bug across this entire subtopic — covered in detail above, but it bears repeating because it's easy to write correct-looking code that's subtly wrong.
  • Single-node-tree edge case. Diameter of a single node is 0, not 1 — double check your base case returns the right neutral value (usually 0 for a "height" tracked as edge-count, or the node's own value for a "path sum through here").
  • Negative values breaking sum-based pruning assumptions, as discussed above — always verify the constraints before assuming sums only grow.
  • Confusing "path" with "root-to-leaf path." Read the problem statement carefully — "any path" almost always means the diameter-shaped, can-bend-anywhere version, which is a meaningfully different (and harder) algorithm than a root-to-leaf variant.
  • Forgetting this pattern generalizes. The "compute per-subtree info, combine at each node, report a single-sided summary upward" shape is the same recursive backbone reused — with memoization added on top — by DP on Trees later in this roadmap, and it shares its "make a choice per node, recurse, combine" structure with the recursive search-tree thinking in Backtracking. Recognizing the shared skeleton across all three topics is worth more than memorizing any individual problem's solution.

Further Resources (Optional)

Practice Problems

Interview relevancy:!!!Critical — must-have!!Important — highly recommended!Good to have~Niche — rarely asked

Optional Practice (Extra Reps)

For once you've cleared the main set above and want more reps on this pattern. These don't count toward the roadmap's progress stats — solve them purely for your own benefit.