Find the Heaviest Path Anywhere in the Tree
Solve this ProblemYou are given the root of a binary tree of integers (which may be negative). A path is a sequence of connected nodes that goes down one side of some node and, optionally, down the other side as well; it can start and end at any nodes and cannot use a node twice. The weight of a path is the sum of its node values. Return the largest weight over all non-empty paths — or 0 if the tree is empty.
The best path that bends at a node uses the better branch on each side of it, ignoring a branch that would lower the sum. Computing those branches bottom-up gives an O(n) solution.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes ≤ 100 - ◆
−100 ≤ node.val ≤ 100 - ◆
The tree is given as its root node (null for an empty tree); each node has a val, a left child and a right child - ◆
A path is a chain of at least one node in which each consecutive pair is joined by a parent-child connection; it may start and end at ANY nodes and may bend once at its highest node (going down one side, then down the other), but it may not visit a node twice. Return the largest sum of node values over all paths (0 for an empty tree). The answer may be negative when every value is negative
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — For Every Node, Re-Measure the Best Branch on Each Side
BruteEvery path has a highest node — the place where it bends (or where it starts, if it does not bend). Through a node, the best path is: the node's own value plus the best downward branch on its left plus the best downward branch on its right, where a branch that would reduce the sum is skipped (use 0 instead). The best downward branch from a node is computed by a helper as: its value plus the better of its two children's branches (or 0). Try every node as the top and keep the maximum. It is correct, but the branch helper re-walks whole subtrees for every ancestor, so it costs O(n²) on a tall tree.
O(n²)O(h)1class Solution {
2 public int bestBendSum(TreeNode root) {
3 if (root == null) return 0;
4 return search(root);
5 }
6
7 private int search(TreeNode node) {
8 if (node == null) return -1000000000;
9 int through = node.val + Math.max(0, down(node.left)) + Math.max(0, down(node.right));
10 return Math.max(through, Math.max(search(node.left), search(node.right)));
11 }
12
13 private int down(TreeNode node) {
14 if (node == null) return 0;
15 return node.val + Math.max(0, Math.max(down(node.left), down(node.right)));
16 }
17}Optimal — One Pass: Return the Best One-Sided Gain, Record the Bend
OptimalDo both jobs in one bottom-up recursion. For a node, get the "gain" from each child (the best downward sum starting at that child) and clip negatives to 0 — a harmful branch is simply not taken. The best path that BENDS at this node is value + left gain + right gain, so compare it with a running best. What the node hands to its parent is different: a path continuing upward cannot fork, so it can use only ONE side — value + the larger of the two gains. Each node does O(1) work, so the total is O(n) with O(h) recursion space. Start the running best at a very small number, so an all-negative tree returns its largest single node.
O(n)O(h)1class Solution {
2 private int best;
3
4 public int bestBendSum(TreeNode root) {
5 if (root == null) return 0;
6 best = Integer.MIN_VALUE;
7 gain(root);
8 return best;
9 }
10
11 private int gain(TreeNode node) {
12 if (node == null) return 0;
13 int left = Math.max(0, gain(node.left));
14 int right = Math.max(0, gain(node.right));
15 best = Math.max(best, node.val + left + right);
16 return node.val + Math.max(left, right);
17 }
18}