Problem overview
The function maxPathSum receives the root of a binary tree (the lesson provides TreeNode, with Val, Left and Right) and returns the largest sum of any path in it. A path is a sequence of nodes where each node is joined by an edge to the next, no node appears twice, the path has at least one node, and it doesn't have to pass through the root. Its sum is the sum of the node values on it.
For the tree with root 1 and children 2 and 3, the best path is 2, 1, 3 with sum 6. For the tree with root -10, a left child 9 and a right child 20 that has children 15 and 7, the best path is 15, 20, 7 with sum 42: continuing up to the root would add -10 and lower the total. For the tree with root -2 and children -1 and -3, every value is negative, so the best path is the single node -1, and the answer is -1.
Approach: every node as the top of a path
Every path has a highest node, the one closest to the root. The path comes up one side to it and goes down the other, so it bends at most once, at that node. That suggests trying each node as the highest node, computing the best path that bends there, and keeping the largest result. Visiting each node once gives O(n) time.
For one node, the best bent path is the node's 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 the node itself. A child's downward path is only worth including if its sum is positive, so each side is clamped at 0: a negative side is simply left out.
The recursion has to return something different from what it records. A parent can extend a path from this node only through one side, because a path that already goes down both sides of this node can't also continue up. So the helper returns the node's value plus the larger of its two clamped sides, and it records the two-sided sum into a shared best.
Step by step
maxPathSum
- Start the best sum at
root.Val, declared with:=. The root alone is a path, so the answer is at least its value. Starting at 0 would be wrong: a path needs a node, and all values can be negative. - Call
maxGain(root, &best). It receives the address ofbestand updates that variable as it walks the tree, so its return value isn't needed here. - Return
best.
maxGain
- Write the signature
func maxGain(node *TreeNode, best *int) int. It returns the largest sum of a path that starts atnodeand goes down, or stops atnode. - Stop at nil. An empty subtree adds nothing to a path, so return 0.
- Get the left side:
max(0, maxGain(node.Left, best)), stored inleft. The clamp at 0 drops a side that would lower the total. - Get the right side the same way into
right. Both children are processed before this node, because the node needs their answers. - Record the path that bends here: set
*bestto the larger of*bestandnode.Val + left + right. - Return the one-way gain:
node.Val + max(left, right).
The solution in Go
func maxPathSum(root *TreeNode) int {
best := root.Val
maxGain(root, &best)
return best
}
func maxGain(node *TreeNode, best *int) int {
if node == nil {
return 0
}
left := max(0, maxGain(node.Left, best))
right := max(0, maxGain(node.Right, best))
*best = max(*best, node.Val+left+right)
return node.Val + max(left, right)
}
Go details worth knowing:
- The built-in
max. Since Go 1.21,maxandminare built in and work on numbers, so no helper function is needed. - A pointer as an accumulator. Go passes arguments by value, so a plain
intparameter would be a copy. Passing&bestgivesmaxGainthe address of the caller's variable, and*bestreads and writes it. The alternative is a package-level variable, but the pointer keeps each call tomaxPathSumindependent. - Nil pointers as the empty tree. A missing child is a
nil*TreeNode, so the base case is the single testnode == nil. The top-level function readsroot.Valdirectly, which is safe because the tree has at least one node. intis 64 bits here. With up to 30,000 nodes of at most 1,000 each, sums stay far from any overflow.
Complexity
Time: O(n), where n is the number of nodes. Each node is visited once and does a constant amount of work.
Space: O(h) for the recursion, where h is the height of the tree. The tree is at most 400 levels deep, so the call stack stays small.
Edge cases and common mistakes
- All values negative. The root of
[-3]alone gives -3. Ifbeststarted at 0, the function would return 0, which is not the sum of any path. - Skipping the clamp. Without
max(0, ...)on the children, a negative subtree is always added. For the tree with root 1, a left child -2 and a right child 3, the correct answer is 4 (1 plus 3), but the version without the clamp returns 3. - Returning the two-sided sum. If
maxGainreturnednode.Val + left + right, a parent would extend a path that already goes down both sides. On the tree with root 1, a left child 2 with children 3 and 4, and a right child 5, the correct answer is 12 (4, 2, 1, 5), while this mistake gives 15, a total that is not a path. - Assuming the path goes through the root. In the second example the best path stays below the root.
- Treating a single node as invalid. A path may be one node, which is why a single value is a candidate answer.
Testing
These results come from running the solution on trees written in level order, with nil for a missing child:
[1, 2, 3]gives 6.[-10, 9, 20, nil, nil, 15, 7]gives 42.[-2, -1, -3]gives -1.[5]gives 5.[-3]gives -3.[2, -1]gives 2.[1, -2, 3]gives 4.[5, 4, 8, 11, nil, 13, 4, 7, 2, nil, nil, nil, 1]gives 48.
