LeetCode 124 ·
Hard
Binary Tree Maximum Path Sum
Find the maximum path sum, where a path is any node sequence along edges.
Try it
Step through the core mechanic. The simulator below runs the tree dp shape this problem is built on.
Walk the pattern
No dedicated step-through for this one yet. The shape is Tree DP — its pattern page has the interactive walkthrough, the reference implementation, and a five-problem progression that this problem sits inside.
The approach
DFS returns the best downward gain from a node: value + max(0, left, right). The best path bending at the node is value + max(0,left) + max(0,right); track that in a global max.
| Aspect | Value |
|---|---|
| Pattern | Tree DP |
| Recognise it by | Best path that may bend at one node. |
| Time complexity | O(n) |
| Space complexity | O(h) |
| Difficulty | Hard |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.