Path sums — longest root-to-leaf sum, largest subtree sum, max non-adjacent sum, K-sum paths

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}