Pattern Guide
Tree Path Problems
"Root-to-leaf paths, path sums, max path through any nodes."
Tree path problems track information along paths from root to leaves or between any two nodes. Key patterns: root-to-leaf path sum (DFS carrying accumulated sum), find all paths equaling target (backtracking DFS), maximum path sum through any node (post-order: max contribution from left/right subtrees), path XOR queries (prefix XOR from root), and diameter of a tree (longest path through any node).
Problems you can solve with this pattern
5 problems · click any to start solving
// 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;
}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).
// 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;
}- 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.