Path sums — longest root-to-leaf sum, largest subtree sum, max non-adjacent sum, K-sum paths
Problem
Four sum problems on a binary tree:
Sum of the longest root-to-leaf path — if two paths are equally long, take the larger sum. Largest subtree sum — the maximum sum of any node plus all its descendants. Maximum non-adjacent sum — pick nodes to maximise the sum, never picking both a parent and its child (House Robber III). K-sum paths — count the downward paths (starting and ending anywhere) whose values sum to k.
Example 1
Input: K-sum: root = [10, 5, -3, 3, 2, null, 11, 3, -2, null, 1], k = 8 Output: 3
5→3, 5→2→1 and −3→11.
Also asked as: Sum of Nodes on the Longest path from root to leaf node · Find Largest subtree sum in a tree · Maximum Sum of nodes in Binary tree such that no two are adjacent · Print all "K" Sum paths in a Binary tree
Test cases
Case 1
Input: [4,2,5,7,1,2,3,null,null,6] Expected: 13
Case 2
Input: [1] Expected: 1
Case 3
Input: [1,2,3] Expected: 4
View solutionHide solution4 approaches
1. Longest root-to-leaf path sum
Time O(n)Space O(h)
DFS returning (length, sum) of the best path; prefer the longer, break ties by larger sum.
function longestPathSum(root) { const dfs = (n) => { if (!n) return [0, 0]; const [ll, ls] = dfs(n.left); const [rl, rs] = dfs(n.right); if (ll > rl || (ll === rl && ls >= rs)) return [ll + 1, ls + n.val]; return [rl + 1, rs + n.val]; }; return dfs(root)[1];}2. Largest subtree sum
Time O(n)Space O(h)
Post-order; each node returns its subtree sum, and a running global max is updated.
function largestSubtreeSum(root) { let best = -Infinity; const sum = (n) => { if (!n) return 0; const s = n.val + sum(n.left) + sum(n.right); best = Math.max(best, s); return s; }; sum(root); return best;}3. Max sum with no two adjacent (tree house robber)
Time O(n)Space O(h)
DFS returns [withNode, withoutNode]. withNode = n.val + left.without + right.without; without = max(left) + max(right).
function maxNonAdjacent(root) { const dfs = (n) => { if (!n) return [0, 0]; const [lw, lwo] = dfs(n.left); const [rw, rwo] = dfs(n.right); return [n.val + lwo + rwo, Math.max(lw, lwo) + Math.max(rw, rwo)]; }; return Math.max(...dfs(root));}4. Print all downward paths summing to K
Time O(n·h)Space O(h)
Carry the path from root; at each node, walk the path backward adding values and print any suffix that sums to K.
function kSumPaths(root, k) { const path = [], res = []; const dfs = (n) => { if (!n) return; path.push(n.val); let sum = 0; for (let i = path.length - 1; i >= 0; i--) { sum += path[i]; if (sum === k) res.push(path.slice(i)); } dfs(n.left); dfs(n.right); path.pop(); }; dfs(root); return res;}