Stage 2: Recursive Thinking·Binary Trees

Hard#1247 min readTreesDFSPostorderLeetCode

Binary Tree Maximum Path Sum

DFS returning best-single-path, tracks any-elbow as side effect

Like diameter but with values. Return one-side max to parent, track global two-side max.

Published Apr 16, 2026

Problem

Given a non-empty binary tree, return the maximum path sum of any path. A path is any sequence of nodes connected by parent-child edges; it does not need to start or end at the root, and it cannot visit a node twice.

Input

root = [1, 2, 3]

Output

Explanation

Path 2 → 1 → 3 sums to 6.

Input

root = [-10, 9, 20, null, null, 15, 7]

Output

Explanation

Path 15 → 20 → 7 sums to 42; the negative root is excluded.

Input

root = [-3]

Output

-3

Explanation

Single node — must include it.

Intuition

This is the diameter problem (#543) with two extra wrinkles:

Sum, not edge count. The contribution of each subtree is its best path sum, not its depth.
Negative paths are optional. If a subtree's best-down sum is negative, don't include it — the path can stop at the current node.

The "elbow" frame still applies: every path has a topmost node where the path enters and exits, possibly going down both sides. So at each node, ask: what's the best sum if my path elbows here? That's node.val + max(0, left_down) + max(0, right_down).

But what we return to our parent is different: the parent can only continue down one side (the path can't fork). So we return node.val + max(0, max(left_down, right_down)).

The clamp max(0, x) is the only nontrivial line in the algorithm.

Approach

DFS, side-effect global max

TimeO(n)

SpaceO(h)

Recommended

A helper returns the best path sum that ends at this node and continues upward through one child. Inside the helper, it also updates a closure-captured best with the elbow-here case (both children + node).

Initialize best to i32::MIN so that even all-negative trees produce the correct answer.

use std::cell::RefCell;
use std::rc::Rc;

impl Solution {
    pub fn max_path_sum(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        fn dfs(node: Option<Rc<RefCell<TreeNode>>>, best: &mut i32) -> i32 {
            match node {
                None => 0,
                Some(n) => {
                    let nb = n.borrow();
                    let l = dfs(nb.left.clone(), best).max(0);
                    let r = dfs(nb.right.clone(), best).max(0);
                    *best = (*best).max(nb.val + l + r);
                    nb.val + l.max(r)
                }
            }
        }
        let mut best = i32::MIN;
        dfs(root, &mut best);
        best
    }
}

Rust · runnable

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val ?? 0;
    this.left = left ?? null;
    this.right = right ?? null;
  }
}

function maxPathSum(root: TreeNode | null): number {
  let best = -Infinity;
  const dfs = (node: TreeNode | null): number => {
    if (node === null) return 0;
    const l = Math.max(0, dfs(node.left));
    const r = Math.max(0, dfs(node.right));
    best = Math.max(best, node.val + l + r);
    return node.val + Math.max(l, r);
  };
  dfs(root);
  return best;
}

TypeScript · runnable

Pure recursion returning (best_down, best_anywhere)

TimeO(n)

SpaceO(h)

Same algorithm, no shared mutable state. Each call returns the pair (best path that goes down through this node clamped at 0, best path seen anywhere in this subtree). The merge step combines child pairs into the parent pair.

Slightly more verbose, but the dataflow is fully explicit — useful for teaching or for when a side effect would be awkward (e.g. parallelizing subtree work).

use std::cell::RefCell;
use std::rc::Rc;

impl Solution {
    pub fn max_path_sum(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        fn dfs(node: Option<Rc<RefCell<TreeNode>>>) -> (i32, i32) {
            match node {
                None => (0, i32::MIN),
                Some(n) => {
                    let nb = n.borrow();
                    let (ld, lb) = dfs(nb.left.clone());
                    let (rd, rb) = dfs(nb.right.clone());
                    let l = ld.max(0);
                    let r = rd.max(0);
                    let here = nb.val + l + r;
                    (nb.val + l.max(r), here.max(lb).max(rb))
                }
            }
        }
        dfs(root).1
    }
}

Rust · runnable

function maxPathSum(root: TreeNode | null): number {
  const dfs = (node: TreeNode | null): [number, number] => {
    if (node === null) return [0, -Infinity];
    const [ld, lb] = dfs(node.left);
    const [rd, rb] = dfs(node.right);
    const l = Math.max(0, ld);
    const r = Math.max(0, rd);
    const here = node.val + l + r;
    return [node.val + Math.max(l, r), Math.max(here, lb, rb)];
  };
  return dfs(root)[1];
}

TypeScript · runnable

Trace

DFS on root = [-10, 9, 20, null, null, 15, 7]:

node	l (clamped)	r (clamped)	here	best after	returns up
9	0	0	9	9	9
15	0	0	15	15	15
7	0	0	7	15	7
20	15	7	42	42	35
-10	9	35	34	42	25

The 42 is captured at node 20 where the path elbows (15 → 20 → 7). The negative root contributes nothing useful — its returned value 25 is dominated by the previously seen 42.

Edge cases

Single node — best initialized to MIN; the single node still gets compared and wins.
All negative values — clamping the children to 0 is what makes "skip this child" possible. Without it, even all-negative trees would force you to add child sums.
Single-side path — returning val + max(l, r) (not val + l + r) is what enforces "no fork on the way up".

Takeaway

Tree DP with two outputs per node is the recurring shape. What you return upward is constrained by what your parent can use; what you record in the global is constrained by the full answer at this subtree. Master that split — you've also handled diameter (#543), longest univalue path, balanced-tree-check, and house-robber-III.

Easy#543

Diameter of Binary Tree

Key insight: the answer might not pass through the root. Track a global max.

Easy#104

Maximum Depth of Binary Tree

1 + max(left_depth, right_depth). This IS the recursive template.

Easy#226

Invert Binary Tree

The simplest recursive tree transformation. Swap left and right, recurse.