The richest path through a tree
A path in a binary tree is a run of nodes in which each node is joined to the next by an edge, and no node is used twice. It has at least one node, and it need not pass through the root. Its sum is the total of its nodes' values.
Return the largest sum of any path in the tree.
- Input
root = [2,-6,8,null,null,-1,5]- Output
15
The path 5, 8, 2 adds up to 15. Going on to -6 or -1 would only lower it.
- Input
root = [-4,-7,-2]- Output
-2
Every value is negative, so the best path is the single largest node.
Limits
1 <= number of nodes <= 20000-1000 <= Node.val <= 1000the tree is at most 3000 levels deep
Hints
Hint 1
For each node, work out the best sum of a path that starts at it and goes down one side. A side worth less than 0 is better left out.
Hint 2
The best path that bends at a node is its value plus the best way down on each side. Track the largest of those as you go.
Where this was reported
- Flipkart, SDE-1 off-campus interview, 2024 (Hashnode)
Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.
Run your code to check it on the examples. Submit runs every hidden test.
