Binary Tree Maximum Path Sum

Q: What is the best time complexity for Binary Tree Maximum Path Sum?

Optimal (postorder with a global best) runs in O(n) time and O(h) extra space. Each node is visited exactly once and does constant work.

Q: Which pattern does Binary Tree Maximum Path Sum use?

It is a trees & bst problem that uses the postorder + multiple return values pattern. Other problems with the same pattern: Balanced Binary Tree, Validate Binary Search Tree, Children Sum in a Binary Tree.

Q: Is there a brute force solution for Binary Tree Maximum Path Sum?

Yes. Brute force (try every turning node) takes O(n²) time and O(h) space. Treat each node as the top of the path.

Q: Which edge cases should I test for Binary Tree Maximum Path Sum?

Every value is negative: the answer is the largest single value; A single node; The best path bends at a node deep inside the tree, not at the root; A skewed tree that is really a linked list.

Hard Trees & BST Postorder + Multiple Return Values Original on LeetCode

Reported atGoogle Amazon Adobe

Binary Tree Maximum Path Sum is a hard trees & bst problem solved with the postorder + multiple return values pattern. The best approach, optimal (postorder with a global best), runs in O(n) time and O(h) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try every turning node) up.

Problem

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

Given the root of a binary tree, return the largest possible sum of node values over all paths.

Examples

Example 1

Input: root = [2, -1, 3]
Output: 5
Why: The path 2 -> 3 sums to 5; adding the -1 child would only lower it.

Example 2

Input: root = [-5, 4, 8, null, null, -2, 6]
Output: 14
Why: The best path is 8 -> 6. Going up through -5 to reach 4 gives only 13.

Example 3

Input: root = [-3]
Output: -3
Why: A path needs at least one node, so a single negative node is the answer.

Constraints

The tree has 1 to 3 * 10^4 nodes.
-1000 <= Node.val <= 1000

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00

Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

Approach	Time	Space
Brute force (try every turning node)	`O(n²)`	`O(h)`
Optimal (postorder with a global best)	`O(n)`	`O(h)`

1Brute force (try every turning node)

TimeO(n²)`down` visits a whole subtree and is called again for every node above it; on a skewed tree that is n + (n-1) + ... + 1.

SpaceO(h)Only the recursion stack, as deep as the tree height h.

Treat each node as the top of the path. The best path through it is its value plus the best non-negative downward chain on each side. Compute those chains from scratch for every node and keep the maximum.

For a node, down(n) = n.val + max(0, down(left), down(right)), and down(null) = 0.
Best path topped at the node = val + max(0, down(left)) + max(0, down(right)).
Recurse into both children and return the largest of the three values.

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 n) {
        if (n == null) return 0;
        return n.val + Math.max(0, Math.max(down(n.left), down(n.right)));
    }
}

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return -(2 ** 31)
        through = root.val + max(0, self.down(root.left)) + max(0, self.down(root.right))
        return max(through, self.maxPathSum(root.left), self.maxPathSum(root.right))

    def down(self, n: Optional[TreeNode]) -> int:
        if n is None:
            return 0
        return n.val + max(0, self.down(n.left), self.down(n.right))

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        if (root == nullptr) return INT_MIN;
        int through = root->val + max(0, down(root->left)) + max(0, down(root->right));
        return max(through, max(maxPathSum(root->left), maxPathSum(root->right)));
    }

private:
    int down(TreeNode* n) {
        if (n == nullptr) return 0;
        return n->val + max(0, max(down(n->left), down(n->right)));
    }
};

function maxPathSum(root) {
    if (root === null) return -Infinity;
    const through = root.val + Math.max(0, down(root.left)) + Math.max(0, down(root.right));
    return Math.max(through, maxPathSum(root.left), maxPathSum(root.right));
}

function down(n) {
    if (n === null) return 0;
    return n.val + Math.max(0, down(n.left), down(n.right));
}

2Optimal (postorder with a global best)

TimeO(n)Each node is visited exactly once and does constant work.

SpaceO(h)Recursion stack of depth h; O(log n) when balanced, O(n) when skewed.

Do one postorder pass. Each call returns the best downward chain starting at its node (so the parent can extend it), and on the way it updates a global answer with the bent path that turns at this node: value plus both non-negative child chains.

gain(null) = 0.
l = max(0, gain(left)), r = max(0, gain(right)).
Update best = max(best, val + l + r).
Return val + max(l, r): a path going up to the parent can use only one side.

class Solution {
    private int best;

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

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

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.best = -(2 ** 31)
        self.gain(root)
        return self.best

    def gain(self, n: Optional[TreeNode]) -> int:
        if n is None:
            return 0
        l = max(0, self.gain(n.left))
        r = max(0, self.gain(n.right))
        self.best = max(self.best, n.val + l + r)
        return n.val + max(l, r)

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        best = INT_MIN;
        gain(root);
        return best;
    }

private:
    int best;

    int gain(TreeNode* n) {
        if (n == nullptr) return 0;
        int l = max(0, gain(n->left));
        int r = max(0, gain(n->right));
        best = max(best, n->val + l + r);
        return n->val + max(l, r);
    }
};

function maxPathSum(root) {
    let best = -Infinity;
    function gain(n) {
        if (n === null) return 0;
        const l = Math.max(0, gain(n.left));
        const r = Math.max(0, gain(n.right));
        best = Math.max(best, n.val + l + r);
        return n.val + Math.max(l, r);
    }
    gain(root);
    return best;
}

Edge cases to test

Every value is negative: the answer is the largest single value
A single node
The best path bends at a node deep inside the tree, not at the root
A skewed tree that is really a linked list

Hints

Hint 1

Every path has one highest node where it turns. For a fixed turning node, the path is that node plus the best downward chain on the left and on the right.

Hint 2

A downward chain that has a negative sum should be dropped: take max(0, chain).

Hint 3

One postorder pass can return the best downward chain to the parent while updating a global best for the bent path at the current node.

FAQ

What is the best time complexity for Binary Tree Maximum Path Sum?

Optimal (postorder with a global best) runs in O(n) time and O(h) extra space. Each node is visited exactly once and does constant work.

Which pattern does Binary Tree Maximum Path Sum use?

It is a trees & bst problem that uses the postorder + multiple return values pattern. Other problems with the same pattern: Balanced Binary Tree, Validate Binary Search Tree, Children Sum in a Binary Tree.

Is there a brute force solution for Binary Tree Maximum Path Sum?

Yes. Brute force (try every turning node) takes O(n²) time and O(h) space. Treat each node as the top of the path.

Which edge cases should I test for Binary Tree Maximum Path Sum?

Every value is negative: the answer is the largest single value; A single node; The best path bends at a node deep inside the tree, not at the root; A skewed tree that is really a linked list.