Binary Tree Maximum Path Sum

Free with account Updated Nov 19, 2026 · 6 min read
On this page

    Problem statement

    Given the root of a binary tree, return the largest sum of any path in it. A path is a chain of nodes where each pair of neighbors is joined by an edge, and no node appears twice. It must contain at least one node, it can start and end anywhere, and it does not have to pass through the root. Node values can be negative.

    This is the classic "hard" tree question, and it shows up often because the fix for the obvious mistake is one line that many candidates can't explain. Original problem: LeetCode 124.

    Example

    The best path is 15 → 20 → 7 with sum 42. It bends at 20 and never touches the root −10.
    The best path is 15 → 20 → 7 with sum 42. It bends at 20 and never touches the root −10.
    Input:  root = [-10, 9, 20, null, null, 15, 7]
    Output: 42        # 15 + 20 + 7
    Input:  root = [-3]
    Output: -3        # all values negative: the answer is the largest single node

    Constraints (assumed)

    • 1 ≤ number of nodes ≤ 30,000.
    • −1,000 ≤ node value ≤ 1,000.

    What this question tests

    • Splitting one hard quantity (best path anywhere) into a simple quantity you can return up (best one-sided path) plus a global answer you update on the way.
    • Handling negative values: when to drop a branch, and why the answer can still be negative.
    • Explaining clearly why the value you return differs from the value you record.

    Questions to ask first

    1. Can values be negative? (Yes. This is the whole difficulty.)
    2. Must the path include the root, or end at a leaf? (Neither.)
    3. Can the path be a single node? (Yes, it needs at least one node.)
    4. How deep can the tree be? A very deep, skewed tree may need an iterative DFS to avoid a stack overflow.