Start learning free

LESSON 406 OF 536 · BINARY TREES

Binary Tree Maximum Path Sum in JavaScript: DFS in O(n)

Practice O(n) Read the full explanation

A path in a binary tree is a sequence of nodes where each node is connected by an edge to the next one, and no node appears twice. A path has at least one node, and it doesn't have to go through the root.

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

Given the root of a binary tree, return the largest path sum of any path in the tree.

The trees below are written in level order (top to bottom, left to right), with null for a missing child.

Example 1:

    1
   / \
  2   3

Input: root = [1,2,3]
Output: 6
Explanation: The best path is 2 → 1 → 3, with the sum 2 + 1 + 3 = 6.

Example 2:

   -10
   /  \
  9    20
      /  \
     15   7

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The best path is 15 → 20 → 7, with the sum 15 + 20 + 7 = 42. Going on to the root would add -10 and lower the sum.

Example 3:

   -2
   /  \
 -1    -3

Input: root = [-2,-1,-3]
Output: -1
Explanation: Every value is negative, so every longer path has a smaller sum. The best path is the single node -1.

Constraints:

The number of nodes in the tree is in the range [1, 3 * 10⁴].
Each node value is between -1000 and 1000.
The tree is at most 400 levels deep.

Note:

The solution should run in O(n) time, where n is the number of nodes: visit each node once.

STEP 1 OF 9

Guided

Ctrl + Enter to check

JAVASCRIPT · BINARY TREES

Binary Tree Maximum Path Sum in JavaScript, explained

Problem overview

The method maxPathSum(root) receives the root of a binary tree with at least one node and returns the largest sum of any path in it. A path is a chain of nodes joined by edges, with no node twice, and at least one node. It doesn't have to pass through the root. The lesson provides the TreeNode constructor, which sets val and starts left and right as null.

In the tree [1, 2, 3] the best path is 2, 1, 3 with sum 6. In [-10, 9, 20, null, null, 15, 7] it is 15, 20, 7 with sum 42, because adding the root would subtract 10. In [-2, -1, -3] every value is negative, so the best path is the single node -1.

Approach: every node gets a turn as the top of a path

Any path has a highest node, the one closest to the root, and it bends only there: it comes up one side of that node and goes down the other. So one pass can try each node as the top and keep the best sum seen.

For a node, the best path with that node on top is its own value plus the best downward path into the left child plus the best downward path into the right child. A downward path starts at a node and goes down through one child at a time, or stops at once. If a side's best downward path is negative, leaving it out is better, so each side counts as at least 0.

The recursion has to report something to the parent too, and that is where a mistake is easy. The parent can extend only one of this node's sides, because a path can't go down both sides and also up. So the helper returns the node's value plus the larger side, not both.

Every node is visited once, giving O(n) time. A brute force that tries every pair of nodes as endpoints would be far slower.

Step by step

Start this.best at root.val. The root alone is a path, and every value might be negative, so 0 isn't a safe starting point. A property on this is visible to every method of the object, so the helper can update it.
Call this.maxGain(root). The call updates this.best on its way through the tree, so its return value isn't used here.
Return this.best.
Declare maxGain(node). It returns the largest sum of a path that starts at node and goes down, or stops at node.
Return 0 for null. An empty subtree adds nothing, and this ends the recursion.
Compute left as Math.max(0, this.maxGain(node.left)), so a negative gain is dropped.
Compute right the same way. Both children are processed before the node itself.
Update this.best with node.val + left + right if that is larger. This is the path that bends at node.
Return node.val + Math.max(left, right), the best one-way path the parent can extend.

The solution in JavaScript

class Solution {
    maxGain(node) {
        if (node === null) {
            return 0;
        }
        let left = Math.max(0, this.maxGain(node.left));
        let right = Math.max(0, this.maxGain(node.right));
        this.best = Math.max(this.best, node.val + left + right);
        return node.val + Math.max(left, right);
    }

    maxPathSum(root) {
        this.best = root.val;
        this.maxGain(root);
        return this.best;
    }
}

For the tree [-10, 9, 20, null, null, 15, 7] the nodes finish in this order, and the printed values are what maxGain sees at each one:

node	left	right	best so far	returns
9	0	0	9	9
15	0	0	15	15
7	0	0	15	7
20	15	7	42	35
-10	9	35	42	25

The root's own row shows the idea: its bend, -10 + 9 + 35, is 34, which doesn't beat 42, and the value it returns, 25, is never used, because the root has no parent.

The JavaScript details worth knowing:

State on this. this.best doesn't exist until maxPathSum sets it, and a property that was never set reads as undefined. That is why maxPathSum assigns it before calling the helper. It also means each call starts from the new root's value rather than from an earlier result.
Math.max takes any number of arguments. Math.max(0, gain) is a compact way to write "gain, but at least 0".
Methods and this. The helper is called as this.maxGain(...), so this inside it is the same object and sees the same best.
Numbers. Sums stay far inside the safe integer range: at most 30,000 nodes of absolute value 1000.

Complexity

Time: O(n). maxGain runs once per node and does constant work besides the two recursive calls.

Space: O(h), where h is the height of the tree: one call per level on the recursion stack. The constraints limit the height to 400 levels, so the recursion is safe.

Edge cases and common mistakes

All values negative. The tree [-3] gives -3, and [-2, -1, -3] gives -1. Starting best at 0 would wrongly return 0.
A single node. [5] gives 5.
A negative branch. In [1, -2, 3] the left child is dropped, and the best path is 1 and 3 with sum 4.
The best path avoids the root. This is the case in [-10, 9, 20, null, null, 15, 7]: the answer is 42, found at the node 20.
Returning both sides to the parent. A version that returns node.val + left + right reports a path that can't exist. On [1, 2, 3, 4, 5] it returns 15, adding all five nodes, while the correct answer is 11 (4, 2, 5).
Not clamping at 0. A negative child would be added to the total even though leaving it out gives a bigger sum.

Testing

[1, 2, 3] gives 6.
[-10, 9, 20, null, null, 15, 7] gives 42.
[-2, -1, -3] gives -1.
[5] gives 5.
[1, -2, 3] gives 4.
[1, 2, 3, 4, 5] gives 11.

Keep going with JavaScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free