Tree DFS (divide and combine)
Recurse into both children, then combine their answers into the answer for this node. Most tree problems are a post-order fold.
TreesO(n) time, O(h) stackNew27 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
height
diameter
path sum
validate a tree property
The template
Get this into muscle memory, then adapt the condition per problem.
function dfs(node) {
if (!node) return base;
const L = dfs(node.left), R = dfs(node.right);
global = combineGlobal(global, L, R, node);
return combineUp(L, R, node);
} Watch Tree Traversals (Pre / In / Post)If you are stuck
The generic hint ladder for this pattern, in order.
- 1What does each child need to tell its parent?
- 2Often the value returned upward differs from the value used for the global answer.
- 3Handle the null node case first and the rest falls out.
Drill it
Every problem in the bank that uses this pattern.
0 / 27 solved