Binary Tree Maximum Path Sum

Hard Problem 78 of 151 Java and Python

Problem

A path in a binary tree is a sequence of nodes where each adjacent pair is connected by an edge, and no node appears twice. It does not need to pass through the root, and it must contain at least one node.

Given the root, return the maximum sum of node values over all paths.

Example 1

Input: root = [1, 2, 3]
Output: 6
Why: The path 2 → 1 → 3.

Example 2

Input: root = [-10, 9, 20, null, null, 15, 7]
Output: 42
Why: The path 15 → 20 → 7.

Constraints

1 ≤ number of nodes ≤ 3 × 10⁴
-1000 ≤ Node.val ≤ 1000

Explanation

Every path has a highest node. The best path through that node is node.val + best downward gain from the left + best downward gain from the right, where a negative gain is replaced by 0 (just do not take that branch).

But a parent can only use one branch of a child, so the value a node returns upwards is node.val + max(leftGain, rightGain). Record the two-branch value in a global best while returning the one-branch value.

Approach 1 · Naive

Try every node as the top

Time O(n²) worst case
Space O(h)

For each node, compute the best downward path from each child from scratch, and combine them.

down(node) = node value + max(0, down(left), down(right)), computed recursively.
For every node, the best path topped there is val + max(0, down(left)) + max(0, down(right)); take the maximum over all nodes.

Java

class Solution {
    public int maxPathSum(TreeNode root) {
        if (root == null) {
            return Integer.MIN_VALUE;
        }
        int through = root.val + Math.max(0, down(root.left)) + Math.max(0, down(root.right));
        return Math.max(through, Math.max(maxPathSum(root.left), maxPathSum(root.right)));
    }

    private int down(TreeNode node) {
        if (node == null) {
            return 0;
        }
        return node.val + Math.max(0, Math.max(down(node.left), down(node.right)));
    }
}

Python

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        def down(node):
            if not node:
                return 0
            return node.val + max(0, down(node.left), down(node.right))

        if not root:
            return float("-inf")
        through = root.val + max(0, down(root.left)) + max(0, down(root.right))
        return max(through, self.maxPathSum(root.left), self.maxPathSum(root.right))

Approach 2 · Optimal

One DFS: return one branch, record two

Time O(n)
Space O(h)

A post-order DFS returns each node's best single-branch gain and updates a global best with the two-branch path through it.

gain(null) = 0.
left = max(0, gain(node.left)), right = max(0, gain(node.right)).
Update best = max(best, node.val + left + right); return node.val + max(left, right).

Java

class Solution {
    private int best;

    public int maxPathSum(TreeNode root) {
        best = Integer.MIN_VALUE;
        gain(root);
        return best;
    }

    private int gain(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = Math.max(0, gain(node.left));
        int right = Math.max(0, gain(node.right));
        best = Math.max(best, node.val + left + right);
        return node.val + Math.max(left, right);
    }
}

Python

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

        def gain(node):
            nonlocal best
            if not node:
                return 0
            left = max(0, gain(node.left))
            right = max(0, gain(node.right))
            best = max(best, node.val + left + right)
            return node.val + max(left, right)

        gain(root)
        return best

Complexity compared

Approach	Time	Space
Naive Try every node as the top	O(n²) worst case	O(h)
Optimal One DFS: return one branch, record two	O(n)	O(h)

Key takeaways

Start best at negative infinity, not 0: a tree of all negative values must return its largest single node.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem