Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

123. Binary Tree Maximum Path Sum

HardDay 36 of 60Trees & BST

A path in a binary tree is a sequence of nodes where each pair of neighbours is joined by an edge, and no node appears twice. The path can start and end anywhere and does not need to pass through the root. Given the root, return the largest possible sum of node values along any non-empty path.

Example 1
Input: root = [1,2,3]
Output: 6
The path 2, 1, 3 has sum 6.
Example 2
Input: root = [-10,9,20,null,null,15,7]
Output: 42
The path 15, 20, 7 has sum 42; including -10 would only lower it.
Constraints
  • The number of nodes is in the range 1 to 3 * 10^4
  • -1000 <= Node.val <= 1000
Hints
Frequently asked at: Meta, Amazon, Google, Microsoft, D. E. Shaw
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for β‚Ή200/ 30 min