Binary Tree Maximum Path Sum
Hard · Trees · Dynamic Programming · Tree · Depth-First Search · Binary Tree
Problem
A path in a binary tree is a chain of nodes where each neighbouring pair is joined by an edge and no node is used twice. It climbs from one end up to a single highest node, where it may turn, and comes back down to the other end. It does not have to pass through the root, and a single node on its own is a path too.
Given the root of a non-empty tree, return the largest sum of values along any path.
Values can be negative, and a path must hold at least one node. So when every value is negative the answer is the largest single value — never 0, and never the empty path.
Trees here are at most 500 levels deep, so a recursive solution is safe.
The node type and two helpers are provided:
Examples
Input: root = [1,2,3] Output: 6
The path 2 → 1 → 3 turns at the root and uses every node: 2 + 1 + 3 = 6.
Input: root = [-10,9,20,None,None,15,7] Output: 42
15 → 20 → 7 turns at 20 and adds up to 42. Stretching it up through the root would add -10 and win back only 9.
Constraints
- 1 <= number of nodes <= 3 * 10^4
- -1000 <= Node.val <= 1000
- the tree is at most 500 levels deep (LeetCode allows a chain of 3 * 10^4; tightened so recursion fits in the browser)
Approaches
- Try every turning point, measuring gains from scratch — time O(n · h), O(n²) worst case, space O(h)
Related problems
Start free on Cariara · Coding problems · System design studio
