Workspace

Problem workspace

3 day streakD

Maximum Path Sum

HardTreesTree properties

The challenge

Find the largest sum of a nonempty simple path, with any endpoints.

Values may be negative. An empty tree returns None/nullopt because no nonempty path exists.

Example

For [−10, 9, 20, null, null, 15, 7], the path 15 → 20 → 7 sums to 42. All-negative example: −2.

Use the walkthrough below to inspect the input and each state change.

See Maximum path sum, step by step

Follow the branches. Watch the state change.

5 input nodesL = left · R = right
Inspect the input.Labels identify node objects; numbers are their values. Left and right child pointers define the tree. Node labels identify objects; numbers show their values. The pointer table below provides the same structure in text.LRLR9B-10A · root15D20C7E
CurrentProcessedPending
View child pointers & node state
Node state · null means no child
NodeValueLeftRightState
A-10BC—
B9nullnull—
C20DE—
D15nullnull—
E7nullnull—
Step 01 / 12

Inspect the input.

Labels identify node objects; numbers are their values. Left and right child pointers define the tree.

root = A:-10
View original input

A:-10 [L:B, R:C] · B:9 [L:null, R:null] · C:20 [L:D, R:E] · D:15 [L:null, R:null] · E:7 [L:null, R:null]

Node IDs stay distinct even when values repeat. Pointer mutations update the diagram; removed nodes remain in the state table for reference.

Put it into code

A path can join two branches locally, but only one branch may continue upward.

Nodes store value, left, and right. C++ uses C++17 or later.

from collections import deque

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def max_path_sum(root):
    if root is None:
        return None
    best = float("-inf")
    def gain(node):
        nonlocal best
        if node is None:
            return 0
        left = max(0, gain(node.left))
        right = max(0, gain(node.right))
        best = max(best, node.value + left + right)
        return node.value + max(left, right)
    gain(root)
    return best

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap