FastPrepMaximum Root-to-Leaf Score
Problems/Maximum Root-to-Leaf Score

Maximum Root-to-Leaf Score

Datadog logoDatadog● MediumFULLTIMENEW GRADPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: The reports ask for the maximum root-to-leaf sum in a tree and discuss iterative traversal, shared parents, and cycles as follow-ups. The parent-array interface, negative and empty cases, examples, and bounds are specified for practice. The core task matches the reports at about 85%.

Each node of a rooted tree has a score. Return the largest sum along a path that starts at the root and ends at a leaf, counting both endpoints.

Node i has score scores[i] and parent parents[i]. The root is node 0, whose parent is -1. A node may have any number of children. A leaf has no children. Parent indices need not be smaller than child indices.

You must reach a leaf, even when scores are negative. A single-node tree returns that node's score. An empty tree returns 0. Use a 64-bit result.

Function

maxRootLeafScore(scores: int[], parents: int[]) → long

Examples

Example 1

scores = [5,4,9,-2,8]parents = [-1,0,0,1,1]return = 17

The root-to-leaf scores are 5 + 4 - 2 = 7, 5 + 4 + 8 = 17, and 5 + 9 = 14. Their maximum is 17.

Example 2

scores = [-5,-2,-8]parents = [-1,0,0]return = -7

The two complete paths score -5 - 2 = -7 and -5 - 8 = -13. Stopping at the root is not allowed because it has children, so the answer is -7.

Example 3

scores = []parents = []return = 0

The tree is empty, so the defined result is 0.

Constraints

  • 0 <= scores.length <= 5000
  • scores.length == parents.length
  • -1000000 <= scores[i] <= 1000000
  • -1 <= parents[i] <= 4999
  • For nonempty input, parents[0] == -1; every other parent is a valid node index. The parent links form one tree rooted at node 0, with no cycle.

More Datadog problems

  • Query Log MatchPHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
  • Delete a Filesystem TreePHONE SCREEN · ONSITE INTERVIEW · Seen Jul 2026
  • Grouped-Query Attention Forward PassPHONE SCREEN · Seen Jun 2026
All Datadog interview questionsSee Datadog hiring insights
Saved
public long maxRootLeafScore(int[] scores, int[] parents) {
    // Write your code here.
}
Checking account…