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 Globalization Partners onsite interview problems in FastPrep.

Is Binary Tree Maximum Path Sum associated with Globalization Partners?

FastPrep tags this as a Globalization Partners 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

Globalization PartnersFULLTIMEONSITE INTERVIEW

Problem statement

A path in a binary tree is a non-empty sequence of nodes in which consecutive nodes share an edge and no node appears more than once. Its sum is the total of its node values.

Given the root of a non-empty binary tree, return the maximum path sum. The path may start and end at any nodes and does not need to pass through the root.

Function

maxPathSum(root: TreeNode) → int

Examples

Example 1

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

The path 2 -> 1 -> 3 uses both children and has sum 6.

Example 2

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

The maximum 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 only valid answer is the root value -3.

Constraints

The tree contains between 1 and 3 * 10^4 nodes.
-1000 <= Node.val <= 1000