FastPrep
Problem · Tree

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

Learn this problem
● MediumUber logoUberINTERNNEW GRADOA
See Uber hiring insights

Problem statement

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.

Function

analyzeTree(values: int[], children: int[][]) → String[]

Examples

Example 1

values = [1, 2, 3]children = [[1, 2], [-1, -1], [-1, -1]]return = ["6", "6", "2 1 3"]

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

Constraints

  • 1 <= n <= 2 * 10^5
  • -10^9 <= values[i] <= 10^9
  • The input forms a valid tree reachable from node 0.

More Uber problems

drafts saved locally
public String[] analyzeTree(int[] values, int[][] children) {
  // write your code here
}
values[1, 2, 3]
children[[1, 2], [-1, -1], [-1, -1]]
expected["6", "6", "2 1 3"]
checking account