FastPrepMaximum Path Sum Between Marked Nodes
Problems/Maximum Path Sum Between Marked Nodes

Maximum Path Sum Between Marked Nodes

DoorDash logoDoorDash● HardFULLTIMEPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: A phone-screen report for a DoorDash machine learning engineer role describes this task. Some leaves of a binary tree are marked, and you find the largest sum of a path between two marked leaves. The report came with a small tree, which is Example 1 here.

The report covers only marked leaves and asks only for the sum. This version adds two practice extensions that the report does not mention: any node can be marked, and you return the path itself. The report also gives no input format or limits, and it does not say what happens with negative values, ties, or fewer than two marked nodes. Here values can be negative, the path is a list of node ids that starts at its smaller end id, ties go to the smallest end ids, and every tree has at least two marked nodes.

The judged task matches the report at about 70%.

A binary tree has n nodes numbered from 0 to n - 1, and node 0 is the root. Node i has the value values[i], the left child left[i] and the right child right[i]. A child of -1 means there is no child on that side.

Some nodes are marked, and marked lists their ids. A marked node can be a leaf or any other node, including the root.

Between two different nodes a and b there is exactly one path: go up from a to the lowest node that has both a and b in its subtree, then go down to b. If one of the two nodes is above the other, the path is just the straight line between them. The sum of a path is the total of the values of all nodes on it, including both ends.

Find the path with the largest sum among all paths whose two ends are two different marked nodes. The nodes in the middle of the path can be marked or not. Return the path as a list of node ids, from one end to the other.

To make the answer unique:

  • Write the ends of a path as (a, b) with a < b. Return the path starting at a and ending at b.
  • If several paths have the largest sum, return the one with the smallest a. If there is still a tie, return the one with the smallest b.

Function

bestMarkedPath(values: int[], left: int[], right: int[], marked: int[]) → int[]

Examples

Example 1

values = [5,2,0,25,14,15]left = [1,3,4,-1,-1,-1]right = [2,-1,5,-1,-1,-1]marked = [3,4,5]return = [3,1,0,2,5]

Only the leaves 3, 4 and 5 are marked, so there are three possible paths:

  • 3 → 1 → 0 → 2 → 4 has sum 25 + 2 + 5 + 0 + 14 = 46.
  • 3 → 1 → 0 → 2 → 5 has sum 25 + 2 + 5 + 0 + 15 = 47.
  • 4 → 2 → 5 has sum 14 + 0 + 15 = 29.

The largest sum is 47. Its smaller end is 3, so the path is listed from 3 to 5.

Example 2

values = [-2,8,3,-4,-1,-6]left = [1,3,-1,-1,-1,-1]right = [2,4,5,-1,-1,-1]marked = [5,1,4]return = [1,4]

Node 1 is marked even though it is not a leaf, so it can be an end. Node 3 is not marked, so no path can end there.

  • 1 → 4 has sum 8 + (-1) = 7.
  • 1 → 0 → 2 → 5 has sum 8 + (-2) + 3 + (-6) = 3.
  • 4 → 1 → 0 → 2 → 5 passes through the marked node 1, which is allowed. Its sum is (-1) + 8 + (-2) + 3 + (-6) = 2.

The largest sum is 7. Node 1 alone would have sum 8, but it does not count, because the two ends must be different nodes.

Example 3

values = [0,5,5,0]left = [1,-1,-1,-1]right = [2,-1,3,-1]marked = [3,2,1]return = [1,0,2]
  • 1 → 0 → 2 has sum 5 + 0 + 5 = 10.
  • 1 → 0 → 2 → 3 has sum 5 + 0 + 5 + 0 = 10.
  • 2 → 3 has sum 5 + 0 = 5.

Two paths tie with sum 10. Their ends are (1, 2) and (1, 3). The smaller ends are both 1, so compare the other ends: 2 is smaller than 3. The answer is the path between 1 and 2, listed from 1.

Constraints

  • n == values.length == left.length == right.length
  • 2 <= n <= 500
  • -1000 <= values[i] <= 1000
  • Each left[i] and right[i] is -1 or a node id from 1 to n - 1.
  • Every node from 1 to n - 1 is the child of exactly one node, and every node can be reached from node 0. So the arrays form one binary tree with root 0.
  • 2 <= marked.length <= n
  • The ids in marked are distinct, and each one is from 0 to n - 1.

More DoorDash problems

  • Customer Bootstrap APIPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Dasher Pay with Store Waits and Peak HoursPHONE SCREEN · Seen Nov 2026
  • Random Dasher Set OperationsONSITE INTERVIEW · Seen Nov 2026
All DoorDash interview questionsSee DoorDash hiring insights
Saved
public int[] bestMarkedPath(int[] values, int[] left, int[] right, int[] marked) {
    // Write your code here.
}
Checking account…