DSA problem
Binary Tree Maximum Path Sum
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 appear in the sequence at most once. 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.
This is a quintessential post-order problem. The trick is to distinguish between two related but different quantities at every node:
- The path sum through the node — the best path that uses the node as its highest point. It looks like
leftBestDown + node.val + rightBestDown, whereleftBestDownandrightBestDownare the best downward paths from the node's children (each clamped to 0 because we are free to ignore a negative-sum branch). - The best downward path from the node — what the node contributes to its parent. This is
node.val + max(leftBestDown, rightBestDown), because a path that continues upward through the parent can only use one of the two children.
We do a single post-order DFS. At each node we compute both quantities; we use (1) to update a global best, and we return (2) upward. The base case is an empty subtree, which contributes 0 to whichever parent calls it (because that parent will clamp anything below 0 anyway).
The algorithm runs in O(n) time (each node visited once) and uses O(h) call-stack space.
Examples
root = [1,2,3]6root = [-10,9,20,null,null,15,7]42root = [-3]-3Constraints
- The number of nodes in the tree is in the range [1, 3 * 10^4].
- -1000 <= Node.val <= 1000
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.