Pattern Reference
Tree Path Problems
"Path sum queries, max/min edge on path, path aggregates with binary lifting."
Loading...
Deep Dive Tutorial
Root-to-leaf path sum: DFS carrying remaining target. At leaf, check if remaining == 0. Backtracking path finding: add node to path, recurse, remove node. Max path sum: at each node, best path through it = node.val + max(0, left_contribution) + max(0, right_contribution). Update global max. Return node.val + max(0, max(left, right)) to parent (can only extend one side upward).
Max path sum and all paths templates
// Maximum path sum through any node
function maxPathSum(root) {
let maxSum = -Infinity;
function dfs(node) {
if (!node) return 0;
const left = Math.max(0, dfs(node.left)); // don't take negative subtrees
const right = Math.max(0, dfs(node.right));
maxSum = Math.max(maxSum, node.val + left + right); // path through this node
return node.val + Math.max(left, right); // extend only one side upward
}
dfs(root);
return maxSum;
}
// Find all root-to-leaf paths summing to target
function pathSum(root, target) {
const result = [], path = [];
function dfs(node, remaining) {
if (!node) return;
path.push(node.val);
if (!node.left && !node.right && remaining === node.val)
result.push([...path]);
dfs(node.left, remaining - node.val);
dfs(node.right, remaining - node.val);
path.pop(); // backtrack
}
dfs(root, target);
return result;
}Worked Problems
sprout
Tree path DFS patterns:
- Root-to-leaf: carry accumulated value down (sum, number formed, XOR)
- Any-path max: post-order, compute contribution at each node, update global
- Count paths = target: prefix sum + HashMap (Path Sum III pattern)
- Backtracking paths: add to path before recurse, pop after
Max path sum trick: At each node, you can take the path through it (left + node + right). But you can only extend one side to parent. So return node + max(left, right, 0) upward.
- Root-to-leaf: carry accumulated value down (sum, number formed, XOR)
- Any-path max: post-order, compute contribution at each node, update global
- Count paths = target: prefix sum + HashMap (Path Sum III pattern)
- Backtracking paths: add to path before recurse, pop after
Max path sum trick: At each node, you can take the path through it (left + node + right). But you can only extend one side to parent. So return node + max(left, right, 0) upward.