# 124. Binary Tree maximum Path Sum Leetcode Solution

## Binary Tree maximum Path Sum Leetcode Problem :

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node’s values in the path.

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

## Binary Tree maximum Path Sum Leetcode Solution :

### Constraints :

• The number of nodes in the tree is in the range [1, 3 * 104].
• -1000 <= Node.val <= 1000

### Example 1:

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

Intuition :

Considering possible paths, We have to select a single path from a subtree root the left, and one to the right, and take the maximum possible answer considering all possible sums between them.

Approach :

• Recursively explore the tree and get leftSum and rightSum.
• At each return point, you have to either return the sum upto the current node from either of the subtrees, since we have to take a single path to which we can add, or just the node itself in case the sub-path is negative.
• The answer could either be the current node, or one of the following three paths:
• Curent node + leftAns
• Current node + rightAns
• leftAns + currentNNode+ rightAns

### Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

## Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others