How should I practice Binary Tree Maximum Path Sum?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Goldman Sachs onsite interview problems in FastPrep.

Is Binary Tree Maximum Path Sum associated with Goldman Sachs?

FastPrep tags this as a Goldman Sachs onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · Tree

Binary Tree Maximum Path Sum

Learn this problem

● Hard

Goldman SachsFULLTIMEONSITE INTERVIEW

Problem statement

Given the root of a non-empty binary tree whose nodes contain integers, return the maximum sum of a non-empty path.

A path is a sequence of distinct nodes where consecutive nodes share an edge. The path may start and end at any nodes and does not need to pass through the root. A node may appear at most once in the path.

Function

maxPathSum(root: TreeNode) → int

Examples

Example 1

root = [1,2,3]return = 6

The path 2 -> 1 -> 3 has sum 6.

Example 2

root = [-10,9,20,null,null,15,7]return = 42

The best path is 15 -> 20 -> 7, whose sum is 42.

Example 3

root = [-3]return = -3

A path must contain at least one node, so the single node is the answer.

Constraints

The tree contains between 1 and 5000 nodes.
Each node value is between -1000 and 1000.
The tree height is at most 1000.