Binary Tree Maximum Path Sum
HardTrees
Given the root of a binary tree, choose any chain of nodes joined by edges, each node used at most once. It can be a single node, and it need not touch the root. Return the largest total of values a chain can have.
On this page a tree is written in level order, top to bottom and left to right, with null where a child is missing: [6, 3, 8, 1] is 6 with children 3 and 8, and 3 with a left child 1.
Examples
Input: root = [-3, 4, -1, 6, 2, null, 5] Output: 12
The path 6 → 4 → 2 sums to 12 and bends at 4. Going on up through -3 and -1 to 5 gives only 6 + 4 - 3 - 1 + 5 = 11.
Input: root = [-4, 6, 7] Output: 9
Passing through -4 still pays: 6 + (-4) + 7 = 9, more than 7 alone.
Constraints
- The tree has 1 to 3 × 10⁴ nodes.
-1000 ≤ node.val ≤ 1000
Stuck?
Hint 1
Every path has one highest node, where it bends. At that node, the best path is its value plus the best path down into the left side plus the best path down into the right, and a side that sums below zero is better left out.
Hint 2
Write a recursion that returns the best path going straight down from a node: its value plus the larger of its children’s results, counting a negative result as 0. On the way, update a running best with the path that bends at the node.
The idea
Every path has one highest node where it bends, joining a path down its left side with a path down its right. For each node, work out the best path that runs straight down from it, and the best path bending there is its value plus both sides, leaving out a side whose total is negative.
Time O(n)Extra space O(h) for a tree of height h
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 6
best starts below any possible total, not at 0. When every value is negative, the answer is the least negative single node.
function maxPathSum(root) { let best = -Infinity; const gain = (node) => { if (!node) return 0; const left = Math.max(0, gain(node.left)); const right = Math.max(0, gain(node.right)); best = Math.max(best, node.val + left + right); return node.val + Math.max(left, right); }; gain(root); return best;}The trap
Keeping a child's total even when it is negative makes every path go down both sides. When a branch below a node adds up to less than 0, the best path should stop at the node, but this version adds the loss in. It works on trees of positive values and fails once a negative branch hangs off the best path.
function maxPathSum(root) { let best = -Infinity; const gain = (node) => { if (!node) return 0; // keeps a child's sum even when it is negative const left = gain(node.left); const right = gain(node.right); best = Math.max(best, node.val + left + right); return node.val + Math.max(left, right); }; gain(root); return best;}