FastPrepFastPrep
Problem Brief

Binary Tree: Subtree Sum, Maximum Path Sum, and Path Nodes

INTERNNEW GRADOA

Given a binary tree where each node stores an integer value, compute three results for the same tree.

  • the sum of all node values
  • the maximum path sum, where a path may start and end at any nodes and must follow parent-child edges
  • one path that achieves the maximum path sum, written as node values from start to end

The tree is encoded with two arrays. values[i] is the value of node i. children[i] = [left, right] stores the child indices of node i, and -1 means that child does not exist. Node 0 is the root.

Return a String[] of length 3 containing the total sum, the maximum path sum, and one maximum path as space-separated node values.

1Example 1

Input
values = [1, 2, 3], children = [[1, 2], [-1, -1], [-1, -1]]
Output
["6", "6", "2 1 3"]
Explanation

The tree sum is 1 + 2 + 3 = 6. The best path is 2 -> 1 -> 3, which also sums to 6.

Constraints

Limits and guarantees your solution can rely on.

  • 1 <= n <= 2 * 10^5
  • -10^9 <= values[i] <= 10^9
  • The input forms a valid tree reachable from node 0.
public String[] analyzeTree(int[] values, int[][] children) {
  // write your code here
}
Input

values

[1, 2, 3]

children

[[1, 2], [-1, -1], [-1, -1]]

Output

["6", "6", "2 1 3"]

Sign in to submit your solution.