HardDynamic ProgrammingTreeDepth-First SearchBinary Tree

Binary Tree Maximum Path Sum

1 approach, code in every language

A path in a binary tree is any sequence of nodes in which each consecutive pair is connected by a parent-child edge. A node may appear in a path at most once, and the path is not required to pass through the root. The path sum is the total of the values of the nodes on that path.

Given the root of a binary tree, return the maximum possible path sum over all paths in the tree. Every tree has at least one node, so at least one path always exists.

Example 1

Input: root = [1,2,3]

Output: 6

The optimal path is 2 -> 1 -> 3 with a sum of 2 + 1 + 3 = 6.

Example 2

Input: root = [-10,9,20,null,null,15,7]

Output: 42

The optimal path is 15 -> 20 -> 7 with a sum of 15 + 20 + 7 = 42; the negative root is skipped.

Constraints

The number of nodes in the tree is in the range [1, 3 * 10^4].
-1000 <= Node.val <= 1000

DFS Returning Maximum Downward Gain

For each node compute the best gain from a straight downward path, and update a global best with the path that splits left-through-node-to-right.

Loading animation…

Intuition

The trick is to separate two ideas: what a node can contribute to its parent versus what the best path through that node looks like. A node can only hand its parent a straight line going down one side, so the gain it returns is node.val plus the larger of its two children's gains (and we clamp a child's gain to zero when it is negative, since including a negative branch never helps). Meanwhile, the best path that peaks at this node may fan out through both children, so we form node.val + leftGain + rightGain and compare it against a running global maximum. Every node gets a chance to be the highest point of the answer path. A single post-order traversal computes both quantities in one pass.

Algorithm walkthrough

1Keep a global best value, initialized so any real path can beat it.
2Define gain(node): if the node is null, return 0 (a missing branch adds nothing).
3Recursively compute leftGain and rightGain, replacing any negative result with 0.
4Update best with node.val + leftGain + rightGain, the value of a path that bends through this node.
5Return node.val + max(leftGain, rightGain) so the parent can extend a single straight branch.
6Call gain(root) to populate best, then return best.

Implementation

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.best = float('-inf')

        def gain(node: Optional[TreeNode]) -> int:
            if not node:
                return 0
            left = max(gain(node.left), 0)
            right = max(gain(node.right), 0)
            self.best = max(self.best, node.val + left + right)
            return node.val + max(left, right)

        gain(root)
        return self.best

Time

O(n)

Space

O(h)

A single post-order pass touches each node once. The recursion stack uses O(h) space, where h is the tree height (O(log n) balanced, O(n) skewed).

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Trees & BST

After the pattern

Now solve one you haven't seen.

Best Chamber Run is our own problem on the technique behind Binary Tree Maximum Path Sum: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free