Problem overview
The function maxPathSum receives the root of a binary tree and returns the largest path sum of any path in it. A path is a sequence of nodes joined by edges, with no node repeated. It needs at least one node, and it doesn't have to pass through the root. The lesson provides the TreeNode class: a node has an Int field value and nullable left and right children.
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, left child 9 and right child 20, where 20 has children 15 and 7, the best path is 15, 20, 7 with sum 42: adding the root would only subtract 10. When every value is negative, as in the tree -2 with children -1 and -3, the best path is the single node -1.
Approach: every path has a highest node
Each path in a tree goes up from some node to a highest node and then down again. It can bend at most once, at that highest node. So the answer is the best value, over all nodes, of "this node as the highest point of a path".
For a node, that best path takes the node's own value plus the best downward path into the left child plus the best downward path into the right child. Each of those downward gains is allowed to be empty, because a side with a negative total only lowers the sum, so it is replaced by 0.
The helper maxGain(node) computes the best sum of a path that starts at node and goes down through one child at a time, or stops at node. It does two jobs at once:
- it updates
bestwith the bent path throughnode, using both sides; - it returns only the one-sided gain, since the parent can extend a single side. A path that took both sides of this node can't also go up to the parent without visiting the node twice.
Each node is visited once, so the time is O(n).
Step by step
- Keep the best sum in a property of the class,
var best = 0, so both methods can use it. - In
maxPathSum, startbestat the root's value,root!!.value. The!!says the root isn't null, which the lesson guarantees. Starting at 0 would be wrong: a tree of negative values has no path with a sum of 0, and the answer must be a real path. - Call
maxGain(root). Its return value isn't needed here; the call exists for its effect onbest. - Return
best. - Write
maxGain(node: TreeNode?): Int. For anullnode, return 0: an empty subtree adds nothing. - Get the left and right gains, each as
maxOf(0, maxGain(child)). Both children are done before the node itself. - Update
bestwithmaxOf(best, node.value + left + right). This is where a path can bend. - Return
node.value + maxOf(left, right), the best path that continues upward through one side only.
The solution in Kotlin
class Solution {
var best = 0
fun maxGain(node: TreeNode?): Int {
if (node == null) {
return 0
}
val left = maxOf(0, maxGain(node.left))
val right = maxOf(0, maxGain(node.right))
best = maxOf(best, node.value + left + right)
return node.value + maxOf(left, right)
}
fun maxPathSum(root: TreeNode?): Int {
best = root!!.value
maxGain(root)
return best
}
}
The Kotlin details worth a closer look:
- A property as shared state.
var best = 0belongs to theSolutionobject, somaxGaincan update it while recursing. BecausemaxPathSumassignsbestbefore every search, a second call on the same object starts fresh: calling it on the tree[1, 2, 3]and then on a single node-3returns 6 and then -3. maxOfis a standard function that returns the larger of two values. It works onIntand many other types.- Smart cast. After
if (node == null) return 0, Kotlin treatsnodeasTreeNodein the rest of the function, sonode.leftandnode.valueneed no?.or!!. root!!.valueasserts non-null. It would throw aNullPointerExceptionfor anullroot, which the constraints exclude.Intis enough. At most 30,000 nodes with values up to 1,000 give sums of at most 30,000,000, far below the 32-bit limit.
Complexity
Time: O(n). maxGain runs once per node, plus once per missing child, and each call does constant work.
Space: O(h), where h is the height of the tree, for the recursion stack. The tree is at most 400 levels deep, so the recursion is shallow enough. A path of 400 nodes, each with value 1, gives 400.
Edge cases and common mistakes
- All negative values. The tree
[-2, -1, -3]gives -1. Startingbestat 0 would return 0, a sum no path has. - A single node.
[5]gives 5 and[-3]gives -3. - Not clamping at 0. Without
maxOf(0, ...), a negative subtree gets added to the path even though leaving it out is better. - Returning both sides to the parent. The return value of
maxGainusesmaxOf(left, right). Adding both would build a path that forks, which isn't a path. - Assuming the path goes through the root. In
[-10, 9, 20, null, null, 15, 7]the best path, 42, skips the root. - A path that doesn't reach the leaves. A path may stop anywhere. In
[2, -1]the answer is 2, not 1.
Testing
Trees are written in level order, with null for a missing child.
[1, 2, 3]gives6.[-10, 9, 20, null, null, 15, 7]gives42.[-2, -1, -3]gives-1.[5]gives5.[-3]gives-3.[2, -1]gives2.[1, -2, 3]gives4.[-1, 5, null, 4, null, 3]gives12.
