Binary Tree Maximum Path Sum

Find the largest sum of any connected path in a binary tree.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Binary Tree Maximum Path Sum: Postorder returns one extendable branch to a parent while scoring a complete path through each node with both nonnegative child gains.

Input and goalFind the largest sum of any connected path in a binary tree.

Initialize at the root valueFor the shown tree, set global best = -10. Postorder must finish child gains before scoring each parent.

7091152203call root-10 root4-4 leaf5

callStackone_branch(-10)best-10nextdescend leftactiveStatecall roottopologyroot -> 9, root -> 20, 9 -> leaf, 20 -> 15, 20 -> 7

Recognize it

Use it when a connected tree path may bend once at a highest node, while any value returned to a parent must remain a single non-branching chain.

Keep true

After a node finishes, its return is the maximum sum of one downward branch starting there; global best is the maximum complete path in every finished subtree, and negative child returns contribute zero.

Reuse it

In tree DP, separate what a parent is allowed to extend from what may finish at the current node; clamp harmful optional branches, return the extendable shape, and update a global answer with the richer local shape.

Pattern: Return one branch, score two branches.

Simple idea: A parent path can use only one branch from a child. A path whose highest node is the current node can use both branches. Return one branch, but use both when updating the full answer.

def max_path_sum(root: TreeNode | None) -> int:
   if root is None:
      return 0

   best = root.val

   def one_branch(node: TreeNode | None) -> int:
      nonlocal best
      if node is None:
         return 0

      left = max(0, one_branch(node.left))
      right = max(0, one_branch(node.right))
      best = max(best, node.val + left + right)
      return node.val + max(left, right)

   one_branch(root)
   return best

Cost: $O(n)$ time and $O(h)$ call-stack space.

The platform supplies TreeNode with val, left, and right; this snippet assumes that definition.