ORIGINAL CODING QUESTION
Best root-to-leaf evidence weight
Nodes have signed weights. Return the maximum sum on a ROOT-TO-LEAF path, including endpoints. Do not stop early at an internal node.
Original exercise · medium. Editorial role relevance does not imply a company has asked this question.
Input and output
n, followed by n parent IDs. Node 0 is root with parent -1; every other parent is in [0, node ID). Then n signed node weights.
Constraints
1 ≤ n ≤ 200; the parent list describes one connected rooted tree. -100 ≤ weight ≤ 100.
Example 1
Input
3 -1 0 0 5 -2 4
Output
9
The path to node 2 has sum 9.
Example 2
Input
2 -1 0 5 -9
Output
-4
The only root-to-leaf path sums to -4.
Explain your approach
Explain your time and auxiliary space complexity. Which input makes your algorithm work hardest?
Private grading inputs, expected outputs and canonical reference implementations are withheld. Authored expected outputs were cross-checked with independent reference oracles; compiler/runtime behavior still needs a verified execution provider.
Hint 1
Each child inherits its parent’s path sum.
Hint 2
Negative weights still count on the required path.
Hint 3
Compare only sums ending at leaves.
Practice this question
Save your work privately, explain decisions and return to your revision queue.
Open practice workspaceBrowse the question library →