Skip to content

089 — Binary Tree Maximum Path Sum

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 2 revisions

89 — Binary Tree Maximum Path Sum

LeetCode 124 · Hard. Given the root of a binary tree, return the maximum path sum of any non-empty path — a path is any sequence of nodes connected by parent-child edges, and it does not need to pass through the root, and need not go in a straight line down.

🍽️ Intuition

This is Diameter of Binary Tree's older, harder sibling. A path's peak (its highest point) can be any node in the tree, and from that peak the path is free to bend down into the left child's best branch and the right child's best branch at the same time — but once the path continues past that peak up to the peak's own parent, it can only carry the value from one side, because a path can't branch twice. So every node needs to answer two different questions: "what's the best path sum if this node is the peak (allowed to use both children)?" and "what's the best sum I can hand up to my parent if I'm just one link in a longer chain (only one child allowed)?"

🚩 Pattern-Recognition Cue

"Maximum path sum" / "path doesn't need to pass through the root" / "may bend at any node" is the same shape as Diameter of Binary Tree and Balanced Binary Tree: a value needs to be checked at every node using its children's already-computed results, which means a single post-order DFS pass that returns one value upward (the best one-branch sum, for the parent's use) while updating a separate global "best answer so far" as a side effect (the best two-branch sum, which may include this node as a peak).

🐢 Brute Force

For every node, treat it as a candidate peak and separately recompute — from scratch, via a plain recursive helper — the best downward path sum starting at each of its two children, then combine. That "best downward sum" helper gets re-run in full for every node that considers using it.

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int) { self.val = val }
}

func collectAllNodes(_ node: TreeNode?, _ result: inout [TreeNode]) {
    guard let node = node else { return }
    result.append(node)
    collectAllNodes(node.left, &result)
    collectAllNodes(node.right, &result)
}

// recomputes the best downward path sum starting at `node`, from scratch, every call
func maxDownwardSum(_ node: TreeNode?) -> Int {
    guard let node = node else { return 0 }
    let leftSum = max(0, maxDownwardSum(node.left))
    let rightSum = max(0, maxDownwardSum(node.right))
    return node.val + max(leftSum, rightSum)
}

func maxPathSumBruteForce(_ root: TreeNode?) -> Int {
    guard let root = root else { return 0 }

    var allNodes: [TreeNode] = []
    collectAllNodes(root, &allNodes)

    var best = Int.min
    for node in allNodes {
        let leftSum = max(0, maxDownwardSum(node.left))
        let rightSum = max(0, maxDownwardSum(node.right))
        best = max(best, node.val + leftSum + rightSum)
    }
    return best
}

// smoke test: -10 -> (9, 20 -> (15, 7))  — best path is 15 -> 20 -> 7, sum 42
let bfRoot = TreeNode(-10)
bfRoot.left = TreeNode(9)
bfRoot.right = TreeNode(20)
bfRoot.right?.left = TreeNode(15)
bfRoot.right?.right = TreeNode(7)
print(maxPathSumBruteForce(bfRoot))   // 42

Big-O: O(n²) time in the worst case — every one of the n nodes considered as a peak triggers a fresh maxDownwardSum call into each of its subtrees, and those calls re-walk potentially large chunks of the tree, giving the same skewed-tree blowup as Diameter of Binary Tree. O(h) extra space for the recursion stack at any given moment.

🚀 Optimal

Do a single post-order DFS. Each call returns the best sum of a path that goes downward from this node through at most one child (what the parent is allowed to use), while updating a captured best variable with the best sum of a path that peaks at this node and is allowed to use both children.

func maxPathSum(_ root: TreeNode?) -> Int {
    var best = Int.min

    @discardableResult
    func dfs(_ node: TreeNode?) -> Int {
        guard let node = node else { return 0 }

        let leftGain = max(0, dfs(node.left))
        let rightGain = max(0, dfs(node.right))

        // this node as the PEAK of a path — allowed to use both children at once
        best = max(best, node.val + leftGain + rightGain)

        // what this node can hand UP to its parent — only one branch allowed
        return node.val + max(leftGain, rightGain)
    }

    dfs(root)
    return best
}

// smoke test: same tree as above
let root = TreeNode(-10)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right?.left = TreeNode(15)
root.right?.right = TreeNode(7)
print(maxPathSum(root))   // 42

// all-negative tree: -3 -> (-2)  — best path is just the single node -2
let negatives = TreeNode(-3)
negatives.left = TreeNode(-2)
print(maxPathSum(negatives))   // -2

// single node
print(maxPathSum(TreeNode(5)))   // 5

Big-O: O(n) time — every node's "best downward gain" is computed exactly once, during the single post-order pass. O(h) extra space for the recursion stack.

🔑 The Key Insight

The brute force's waste is identical in spirit to Diameter of Binary Tree's: it re-derives "best downward sum from this point" from scratch for every candidate peak, even though that value is already available the moment a node's children finish their own post-order calls. The optimal version separates two genuinely different questions that the brute force conflates into one re-derived quantity: "what can I offer my parent" (one branch only — return) versus "what's my best score as the tallest point of a path" (both branches allowed — folded into the best side-channel). Computing both, once, in the same bottom-up pass is what turns O(n²) into O(n) — using max(0, ...) on each child's gain is what lets a path simply exclude a branch entirely when it would only hurt the sum, including on all-negative trees.

🔗 Related Chapters

  • Binary Trees — the structure the path bends through.
  • DFS and Backtracking — the single post-order pass that returns an upward value while updating a side-channel global.
  • Diameter of Binary Tree — the same "peak value at every node, combine both children, single bottom-up pass" shape, just summing values here instead of counting edges.

🧸 Memory Sentence

Maximum Path Sum is asking every node two questions at once — "what can I hand up to my parent" (pick one branch) and "what's my best score if the path bends right here" (both branches allowed) — and answering both in a single bottom-up sweep instead of re-measuring from scratch at every candidate peak.

✅ Check Your Understanding

Trace dfs on the tree -10 -> (9, 20 -> (15, 7)) in post-order (left subtree, right subtree, then the node itself). Write out leftGain, rightGain, the return value, and the running best at each of the five calls. Explain why node -10's own return value (what it could hand to a nonexistent parent) is not the final answer, and why best ends up capturing a path that never even touches node -10.

⬅️ Previous: Construct Binary Tree from Preorder and Inorder Traversal · Next: Serialize and Deserialize Binary Tree ➡️

Clone this wiki locally