Binary Tree Maximum Path Sum
The key idea
At each node the answer can bend through it once: best = node.val + max(0, leftGain) + max(0, rightGain). But the value you return to the parent can only continue down ONE side, so return node.val + max(0, max(leftGain, rightGain)). Clamping negative gains to 0 means a harmful subtree is simply dropped.
Problem
You are given the root of a binary tree. A path is any sequence of nodes where each pair of adjacent nodes is connected by an edge, and a node appears in the sequence at most once. The path does not need to pass through the root, and it must contain at least one node. The path sum is the total of the values of the nodes along the path. Return the maximum path sum of any non-empty path in the tree. Node values may be negative, so the best path is not always the largest subtree.
Constraints
- The number of nodes in the tree is in the range
[1, 3 * 10^4]. -1000 <= Node.val <= 1000
Examples
Input: root = [1,2,3]
Output: 6
Input: root = [-10,9,20,null,null,15,7]
Output: 42
Complexity
Time: O(n) Space: O(h)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Tree / Recursion problems
- Balanced Binary TreeEASY
- Binary Tree CamerasHARD
- Binary Tree Inorder TraversalEASY
- Binary Tree PathsEASY
- Binary Tree Postorder TraversalEASY
- Binary Tree Preorder TraversalEASY
- House Robber IIIMEDIUM
- Construct Binary Tree from Inorder and Postorder TraversalMEDIUM
- Construct Binary Tree from Preorder and Inorder TraversalMEDIUM
- Convert BST to Greater TreeMEDIUM
- Count Complete Tree NodesEASY
- Count Good Nodes in Binary TreeMEDIUM