Binary Tree Maximum Path Sum

HARD✓ CHIP-TIMEDLC #124 — FULL STATEMENT ↗

The drill: A path drifts through the tree along parent-child edges and may bend exactly once at its highest point — find the largest sum any such path can reach, with values negative or positive and at least one node in the path.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A path through the tree follows parent-child edges and may bend exactly once, at its own highest point, weaving through one node where it switches from climbing on one side to descending on the other.

Values along the tree can be negative, so a path is free to duck into a single node and stop right there — every path must contain at least one node, but it never needs to touch the root or run all the way to a leaf.

The task is finding the largest sum achievable by any such path and returning that one number.

EX 01

root = [5]

→ 5

SINGLE POSITIVE NODE

EX 02

root = [-3]

→ -3

SINGLE NEGATIVE NODE — MUST STILL PICK IT

EX 03

root = [-2, -1]

→ -1

ALL NEGATIVE — BEST PATH IS THE LONE -1

node values can be negative, zero, or positive
a path always contains at least one node
a path bends at most once, at its own highest point
tree sizes reach into the tens of thousands

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A path doesn't have to touch the root, and it doesn't have to go straight down — it can bend once at its highest point. What does every node need to know about the branches below it to test itself as that bend?

HINT 2 THE STRUCTURE

Separate two questions at each node: what's the best sum of a path that bends here (both children may contribute), versus what's the best sum of a path that only continues upward through here (at most one child may contribute)?

HINT 3 ONE STEP FROM THE ANSWER

At every node take max(0, bestLeftDown) and max(0, bestRightDown) so a losing branch costs nothing. Feed the global best with node.val + left + right, but hand upward only node.val + the better single side.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE BEND POINTPATTERN · POSTORDER, ONE PASSroot = [5, -3, 4]

STEP 1

A path may bend once, at its highest point. Postorder: each node hands upward its best single-branch run while a global best tracks the bend-through-here total.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/binary-tree-maximum-path-sum.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.best = float("-inf")

        def dfs(node):
            if node is None:
                return 0
            left = max(dfs(node.left), 0)
            right = max(dfs(node.right), 0)
            self.best = max(self.best, node.val + left + right)  # bend through here
            return node.val + max(left, right)  # continue upward, one side only

        dfs(root)
        return self.best

TIME O(N)SPACE O(H)PYTHON · RACE PACE · 14 LN

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.best = float("-inf")

        def max_downward(node):
            # best sum of a path starting at node and going straight down —
            # recomputed from scratch for every apex that asks for it
            if node is None:
                return 0
            return node.val + max(0, max_downward(node.left), max_downward(node.right))

        def visit(node):
            if node is None:
                return
            left = max_downward(node.left)
            right = max_downward(node.right)
            self.best = max(self.best, node.val + max(0, left) + max(0, right))
            visit(node.left)
            visit(node.right)

        visit(root)
        return self.best

TIME O(N²)SPACE O(N)PYTHON · TRAINING PACE · 22 LN

class Solution {
    private int best;

    public int maxPathSum(TreeNode root) {
        best = Integer.MIN_VALUE;
        dfs(root);
        return best;
    }

    private int dfs(TreeNode node) {
        if (node == null) return 0;
        int left = Math.max(dfs(node.left), 0);
        int right = Math.max(dfs(node.right), 0);
        best = Math.max(best, node.val + left + right); // bend through here
        return node.val + Math.max(left, right); // continue upward, one side only
    }
}

TIME O(N)SPACE O(H)JAVA · RACE PACE · 17 LN

class Solution {
    private int best;

    public int maxPathSum(TreeNode root) {
        best = Integer.MIN_VALUE;
        visit(root);
        return best;
    }

    private void visit(TreeNode node) {
        if (node == null) return;
        int left = maxDownward(node.left);
        int right = maxDownward(node.right);
        best = Math.max(best, node.val + Math.max(0, left) + Math.max(0, right));
        visit(node.left);
        visit(node.right);
    }

    // best sum of a path starting at node and going straight down —
    // recomputed from scratch for every apex that asks for it
    private int maxDownward(TreeNode node) {
        if (node == null) return 0;
        return node.val + Math.max(0, Math.max(maxDownward(node.left), maxDownward(node.right)));
    }
}

TIME O(N²)SPACE O(N)JAVA · TRAINING PACE · 25 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED