Trees · 072Hard
Binary Tree Maximum Path Sum
A path is any sequence of nodes connected by edges, appearing at most once each, and need not pass through the root. Return the maximum sum of node values along any path.
Constraints
- The tree holds 1 to 3 * 10^4 nodes.
- -1000 <= Node.val <= 1000
- INPUT FORMAT
- `root` is a TreeNode object, not an array. The arrays in EXAMPLES are the level-order
- serialization the platforms print — breadth-first, with `null` for a missing child. The
- test runner builds a real tree from that array before calling your function.
Examples
maxPathSum([1, 2, 3]) -> 6 // 2 + 1 + 3 maxPathSum([-10, 9, 20, null, null, 15, 7]) -> 42 // 15 + 20 + 7 maxPathSum([-3]) -> -3 // all-negative tree maxPathSum([2, -1]) -> 2 // the negative child is dropped maxPathSum([-2, -1]) -> -1 // best is the single largest node maxPathSum([1, -2, -3, 1, 3, -2, null, -1]) -> 3 // the best path avoids the root
Edge cases
- All values negative — the answer is the single largest node, never 0.
Show the target complexity (spoiler)
- Naive
- O(n^2) time — evaluate every possible path from every node.
- Target
- O(n) time, O(h) space — DFS returning the best straight-line downward sum, while separately tracking the best bent path seen.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/07-trees/072-binary-tree-maximum-path-sum.js ./practice c 072