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.
View child pointers & node state
| Node | Value | Left | Right | State |
|---|---|---|---|---|
| A | -10 | B | C | — |
| B | 9 | null | null | — |
| C | 20 | D | E | — |
| D | 15 | null | null | — |
| E | 7 | null | null | — |
Inspect the input.
Labels identify node objects; numbers are their values. Left and right child pointers define the tree.
root = A:-10View 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
#include <algorithm>
#include <cmath>
#include <functional>
#include <limits>
#include <map>
#include <optional>
#include <queue>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
struct Node {
long long value;
Node *left = nullptr, *right = nullptr;
explicit Node(long long v) : value(v) {}
};
optional<long long> max_path_sum(Node* root) {
if (!root) return nullopt;
long long best = numeric_limits<long long>::lowest();
function<long long(Node*)> gain = [&](Node* node) -> long long {
if (!node) return 0;
long long left = max(0LL, gain(node->left));
long long right = max(0LL, gain(node->right));
best = max(best, node->value + left + right);
return node->value + max(left, right);
};
gain(root);
return best;
}