Problem statement

A path in a binary tree is a sequence of nodes where every two consecutive nodes are joined by an edge, and no node appears more than once. A path holds at least one node and does not have to pass through the root.

The path sum is the total of the values of the nodes on the path.

Given the root of a non-empty binary tree, return the largest path sum of any path in it.

Example 1

Input: root = [1,2,3]
Output: 6
Explanation: The path 2 → 1 → 3 adds up to 2 + 1 + 3 = 6.

Example 2

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The path 15 → 20 → 7 gives 42; dragging in -10 and 9 would only lower it.

Example 3

Input: root = [-3]
Output: -3
Explanation: A path needs at least one node, so the only path is the root itself.

Constraints

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

Hints for Binary Tree Maximum Path Sum

1. Hint 1

   Every path has one highest node — the place where it stops going up and starts going down. Try each node as that peak.

2. Hint 2

   For a peak, the best path is its value plus the best downward chain into the left subtree and into the right, each only if it is positive.

3. Hint 3

   One post-order pass can return, for every node, its best downward chain (value plus the better positive child chain) while updating a global answer with value + left + right.

How to solve Binary Tree Maximum Path Sum

Hang every path from its highest node. At that peak the path is the node itself plus, optionally, one chain going down-left and one going down-right — so all we need per node is the best chain that starts there and goes downward, which its children can report.

Approach

1. Define gain(node) = the largest sum of a downward chain that starts at node (0 for a missing child).
2. Compute it post-order: left = max(gain(node.left), 0), right = max(gain(node.right), 0); a negative chain is better left out.
3. Before returning, treat node as a peak: update the answer with node.val + left + right.
4. Return node.val + max(left, right) — a chain that continues upward can take only one side.
5. Start the answer at the root's value and return it after the pass.

Why it works

Every path has exactly one node closest to the root, and the path splits there into at most two downward chains into different subtrees. The best path with that peak takes the best non-negative chain on each side, which is exactly what the update computes; taking the maximum over all peaks covers every path.

Complexity

• Time — O(n)
• Space — O(h) for the recursion, h the height of the tree

Pitfalls

• Starting the answer at 0 is wrong when every value is negative — the answer is then the largest single value.
• The value returned upward may use only one child; the value that updates the answer may use both.
• Clamp a child's chain at 0 rather than skipping the node: the node itself must always be on its own path.

Reference solution

Python

from typing import Optional

def maxPathSum(root: Optional[TreeNode]) -> int:
    best = [root.val]

    def gain(node):
        if node is None:
            return 0
        left = max(gain(node.left), 0)
        right = max(gain(node.right), 0)
        best[0] = max(best[0], node.val + left + right)
        return node.val + max(left, right)

    gain(root)
    return best[0]

Java

public static int maxPathSum(TreeNode root) {
    int[] best = { root.val };
    pathGain(root, best);
    return best[0];
}

static int pathGain(TreeNode node, int[] best) {
    if (node == null) return 0;
    int left = Math.max(pathGain(node.left, best), 0);
    int right = Math.max(pathGain(node.right, best), 0);
    best[0] = Math.max(best[0], node.val + left + right);
    return node.val + Math.max(left, right);
}

C++

int maxPathSum(TreeNode* root) {
    int best = root->val;
    function<int(TreeNode*)> gain = [&](TreeNode* node) -> int {
        if (!node) return 0;
        int left = max(gain(node->left), 0);
        int right = max(gain(node->right), 0);
        best = max(best, node->val + left + right);
        return node->val + max(left, right);
    };
    gain(root);
    return best;
}

JavaScript

var maxPathSum = function(root) {
    var best = root.val;
    var gain = function(node) {
        if (node === null) return 0;
        var left = Math.max(gain(node.left), 0);
        var right = Math.max(gain(node.right), 0);
        best = Math.max(best, node.val + left + right);
        return node.val + Math.max(left, right);
    };
    gain(root);
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More dynamic programming problems

• Maximum Path Sum Between Two Leaves Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Maximum Sum BST in Binary Tree Hard
• Recover a Tree From Preorder Traversal Hard
• Vertical Order Traversal of a Binary Tree Hard
• Binary Tree Cameras Hard