Vineyard Tasting Route
A hillside vineyard is a network of plots joined by footpaths. From the visitor centre plot, at most two paths lead further up the hill, and so on from every plot, with no loops: a binary tree. Each plot has a score from last year's visitors. A great tasting scores high; a muddy, steep plot with a sour wine scores below zero.
The vineyard wants to print its best tasting route: a walk through connected plots that never visits a plot twice, starting and ending anywhere. The route's score is the sum of the plots on it. A route can be a single plot, and it does not have to include the visitor centre.
Your task
Write bestTastingRoute(root). A path is a sequence of nodes where each pair of neighbours is joined by an edge, and no node appears twice. Return the largest possible sum of node values over all non-empty paths in the tree.
The tree always has at least one node. Values can be negative, and so can the answer. Trees are shown in level order, like [-3, 9, 6, null, null, -2, 8], where null marks a missing child. Your function receives real TreeNode objects with val, left and right.
bestTastingRoute(root: TreeNode) → int
Examples
root = [-3, 9, 6, null, null, -2, 8]
20
The best route is 9 → -3 → 6 → 8, scoring 20. It passes through the visitor centre (-3) even though that plot loses points, because it connects 9 with 6 + 8 = 14. Avoiding it, the best is 6 → 8 = 14.
root = [2, -6, -1, 4, 5, -3]
5
Plot 5 alone scores 5. Every longer route that includes it must pass through -6: 4 → -6 → 5 scores 3, and 5 → -6 → 2 scores 1. Here the best route is a single plot, far from the visitor centre.
Constraints
- 1 ≤ number of plots ≤ 1,000
- -1,000 ≤ score ≤ 1,000
- The tree is at most 500 levels deep.
Start with brute force
Try every pair of plots as the two ends of the route, walk the unique path between them, and add up its scores. Keep the best.
With 1,000 plots there are about 500,000 pairs, and each path can be hundreds of plots long, so this runs into the hundreds of millions of steps: O(n²) pairs times O(h) per path. The waste is that neighbouring routes share most of their plots. Computing, for every plot, its best downward walk once, bottom-up, lets every turning point be checked in O(1).
Hints
0 of 4 shown- Hint 1
Every route has one plot closest to the visitor centre, where it turns. In the first example, where does the best route turn, and what does it collect on each side of that plot?
- Hint 2
A route turning at plot X is: the best downward walk into X's left side, plus X, plus the best downward walk into X's right side. Either side can be skipped if it would only lose points.
- Hint 3
So for every plot you want one number: the best score of a walk that starts at that plot and goes straight down (one branch only). How can a plot get that number from its children's numbers?
- Hint 4
Bottom-up:
gain(node) = node.val + max(0, gain(left), gain(right)), with 0 for a missing child. At each node, also update a sharedbestwithnode.val + max(0, gain(left)) + max(0, gain(right)). Return the one-branch gain to the parent, never the two-branch total. Startbestat minus infinity or the root's value, not 0, because every plot might be negative.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Two different numbers are in play at each plot. The gain is the best walk that starts here and goes down one branch; it is what the parent can extend. The route through here uses both branches and turns at this plot; nothing above can extend it, so it only updates the best answer.
Trace [-3, 9, 6, null, null, -2, 8], bottom-up:
- Plot 9 (a leaf): route 9, best = 9. Gain 9.
- Plot -2 (a leaf): route -2, best stays 9. Gain -2, which its parent will treat as 0.
- Plot 8 (a leaf): route 8, best stays 9. Gain 8.
- Plot 6: left gain max(0, -2) = 0, right gain 8. Route 6 + 0 + 8 = 14, best = 14. Gain 6 + 8 = 14.
- Plot -3: left gain 9, right gain 14. Route -3 + 9 + 14 = 20, best = 20. Gain 11, unused.
The answer is 20. Two classic bugs: starting best at 0 (wrong when every plot is negative), and returning node.val + left + right to the parent, which would let a route fork into a Y shape.
function bestTastingRoute(root) {
let best = -Infinity;
// Best score of a walk that starts at node and only goes down.
function gain(node) {
if (node === null) return 0;
const left = Math.max(0, gain(node.left)); // skip a side that loses points
const right = Math.max(0, gain(node.right));
best = Math.max(best, node.val + left + right); // route turning here
return node.val + Math.max(left, right); // parent can use one side only
}
gain(root);
return best;
}def best_tasting_route(root):
best = float('-inf')
# Best score of a walk that starts at node and only goes down.
def gain(node):
nonlocal best
if node is None:
return 0
left = max(0, gain(node.left)) # skip a side that loses points
right = max(0, gain(node.right))
best = max(best, node.val + left + right) # route turning here
return node.val + max(left, right) # parent can use one side only
gain(root)
return bestRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.