Skip to main content
All Questions

Given the root of a binary tree of integers, return the maximum path sum.

Hard

A path in a binary tree is a sequence of nodes where each pair of neighbors is joined by an edge and no node appears more than once. A path doesn't have to pass through the root. Its path sum is the total of the values on it.

Given the root of a binary tree, return the largest path sum of any non-empty path.

Trees in the examples and tests are written in level order, with null for a missing child.

Example 1

Input: root = [1, 2, 3] Output: 6

The best path is 2 -> 1 -> 3.

Example 2

Input: root = [-10, 9, 20, null, null, 15, 7] Output: 42 -10 / \ 9 20 / \ 15 7

The best path is 15 -> 20 -> 7, which skips the root.

Constraints

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

Related courses

Course

Machine Learning Engineer Interview Prep

Land your dream machine learning role at Meta, Google, Amazon, Apple, Microsoft, Nvidia, and other top companies. Learn from mock interviews, frameworks, and advice from senior candidates. Explore ML system design, core concepts, coding, behavioral interviews, and more.

Course

Data Science Interview Prep

Land your dream data science role at Google, Amazon, Microsoft, Meta, Apple, and other top companies. Learn from mock interviews, frameworks, and advice from senior candidates. Practice statistics, experimentation, coding, SQL, machine learning, behavioral interviews, and more.