DSA Binary Tree Maximum Path Sum

The problem

A path in a binary tree is a chain of connected nodes that never branches. A path may start and end at any two nodes. It may also hold a single node.

Each node holds a number, and numbers may be negative. The maximum path sum is the largest total of node values over every path in the tree.

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

tree_a = TreeNode(-10, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
tree_b = TreeNode(-3, TreeNode(-2), TreeNode(-5))
tree_c = TreeNode(5,
                  TreeNode(4, TreeNode(11, TreeNode(7), TreeNode(2))),
                  TreeNode(8, TreeNode(13), TreeNode(4, TreeNode(1))))
for name, expected in [("Tree A", 42), ("Tree B", -2), ("Tree C", 48), ("single node 5", 5)]:
    print(name, "-> maximum path sum:", expected)

Tree B holds only negative values. Its best path is a single node, the least negative one. Tree A's best path bends at node 20, not at the root.

Intuition: only paths through the root

A first attempt looks for the best path that passes through the root. That path takes the root plus the best downward chain on each side. It is a natural first target, and it is too narrow.

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

def downward(node):
    if node is None:
        return 0
    return node.value + max(downward(node.left), downward(node.right), 0)

tree = TreeNode(-5,
                TreeNode(10, TreeNode(20), TreeNode(30)),
                TreeNode(1))
through_root = tree.value + max(downward(tree.left), 0) + max(downward(tree.right), 0)
print("best path through the root:", through_root)
print("the path 20 - 10 - 30 totals:", 20 + 10 + 30)

The root-only method answers 36. The path from 20 to 30 through their parent 10 totals 60 and never touches the root. Every node must be allowed to host the bend of a path, not only the root.

Brute force: bend a path at every node

Every path has one highest node, the node where it bends or its top end. The brute force tries each node as that bend. For each bend it enumerates every downward path on both sides.

A downward path starts at a child and only descends. The bend combines the node with the best downward total on each side, where taking nothing from a side is allowed. A counter records the downward paths generated.

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

def downward_paths(node, counter):
    if node is None:
        return []
    paths = [node.value]
    for child in (node.left, node.right):
        for sub in downward_paths(child, counter):
            paths.append(node.value + sub)
    counter[0] += 1
    return paths

def brute(root):
    counter = [0]
    best = [None]

    def visit(node):
        if node is None:
            return
        left = downward_paths(node.left, counter)
        right = downward_paths(node.right, counter)
        total = node.value + max([0] + left) + max([0] + right)
        if best[0] is None or total > best[0]:
            best[0] = total
        visit(node.left)
        visit(node.right)

    visit(root)
    return best[0], counter[0]

tree_a = TreeNode(-10, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
tree_trap = TreeNode(-5,
                     TreeNode(10, TreeNode(20), TreeNode(30)),
                     TreeNode(1))
for name, tree in [("Tree A", tree_a), ("trap tree", tree_trap)]:
    answer, generated = brute(tree)
    print(name, "-> maximum path sum:", answer, "downward paths generated:", generated)

Both answers match the expected values, 42 and 60. The cost is repetition. The downward paths under a node are rebuilt for every ancestor that asks, and deep trees rebuild them many times.

The optimal solution: one gain returned upward per node

The state is a single shared best, updated at every node. Each node returns its best one-sided gain, its own value plus the better of its two child gains, with any child gain below zero dropped to zero first.

This method is dynamic programming on a tree, called tree DP. Each node returns a small summary of its own subtree to its parent. The parent combines the summaries it receives with its own value, then returns a fresh summary upward.

The same node also offers a two-sided path to the shared best. The offer is the node's value plus both dropped child gains. A path returned upward can only use one side, because a chain cannot branch, so the return takes the larger side alone.

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

def max_path_sum(root):
    best = [root.value]
    visits = [0]

    def gain(node):
        if node is None:
            return 0
        visits[0] += 1
        left = max(gain(node.left), 0)
        right = max(gain(node.right), 0)
        best[0] = max(best[0], node.value + left + right)
        return node.value + max(left, right)

    gain(root)
    return best[0], visits[0]

tree_a = TreeNode(-10, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
tree_b = TreeNode(-3, TreeNode(-2), TreeNode(-5))
tree_c = TreeNode(5,
                  TreeNode(4, TreeNode(11, TreeNode(7), TreeNode(2))),
                  TreeNode(8, TreeNode(13), TreeNode(4, TreeNode(1))))
for name, tree, expected in [("Tree A", tree_a, 42), ("Tree B", tree_b, -2), ("Tree C", tree_c, 48), ("single node 5", TreeNode(5), 5)]:
    answer, visits = max_path_sum(tree)
    print(name, "->", answer, "expected:", expected, "match:", answer == expected, "nodes visited:", visits)

All four cases match. Each node is visited exactly once. The shared best starts at the root value, which is what lets an all-negative tree answer with a single node.

Walkthrough: Tree A from the leaves up

The walk visits Tree A bottom-up. Each line shows one node's clamped child gains, the two-sided path it offers, and the gain it returns upward. The order is the order the recursion returns in.

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

best = [None]

def gain(node):
    if node is None:
        return 0
    left = max(gain(node.left), 0)
    right = max(gain(node.right), 0)
    through = node.value + left + right
    if best[0] is None or through > best[0]:
        best[0] = through
    upward = node.value + max(left, right)
    print("node", node.value, "- left gain:", left, "right gain:", right, "- offers:", through, "- returns:", upward)
    return upward

tree = TreeNode(-10, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
gain(tree)
print("maximum path sum:", best[0])

Node 20 offers 42, from 15 plus 20 plus 7. That offer is the answer. The root offers only 34, because its left gain is just 9, and it returns 25 upward to nobody.

Complexity

The gain walk visits each node once, so its time is O(n) for n nodes. The shared best is one number, and the recursion stack grows with the height of the tree, so the extra space is O(height).

The brute force regenerates downward paths at every ancestor. On balanced trees the counter below shows its generated-path count pulling away from the node count, while the optimal walk's visit count equals the node count exactly.

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

def build(depth):
    if depth == 0:
        return None
    return TreeNode(1, build(depth - 1), build(depth - 1))

def downward_paths(node, counter):
    if node is None:
        return []
    paths = [node.value]
    for child in (node.left, node.right):
        for sub in downward_paths(child, counter):
            paths.append(node.value + sub)
    counter[0] += 1
    return paths

def brute_count(root):
    counter = [0]

    def visit(node):
        if node is None:
            return
        downward_paths(node.left, counter)
        downward_paths(node.right, counter)
        visit(node.left)
        visit(node.right)

    visit(root)
    return counter[0]

def gain_visits(root):
    visits = [0]

    def gain(node):
        if node is None:
            return 0
        visits[0] += 1
        left = max(gain(node.left), 0)
        right = max(gain(node.right), 0)
        return node.value + max(left, right)

    gain(root)
    return visits[0]

for depth in [3, 4, 5]:
    tree = build(depth)
    nodes = 2 ** depth - 1
    print("nodes", nodes, "- brute paths generated:", brute_count(tree), " gain visits:", gain_visits(tree))

At 31 nodes the brute force generated 98 downward paths against 31 visits. The gap widens with height, because each level re-does the work of the levels below it.

Edge cases and pitfalls

A tree of only negative values answers with its least negative node. A negative child gain is dropped, never carried upward. The method expects a real root; an empty tree has no path at all, so no call is made on it here.

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

def max_path_sum(root):
    best = [root.value]
    visits = [0]

    def gain(node):
        if node is None:
            return 0
        visits[0] += 1
        left = max(gain(node.left), 0)
        right = max(gain(node.right), 0)
        best[0] = max(best[0], node.value + left + right)
        return node.value + max(left, right)

    gain(root)
    return best[0], visits[0]

print("all negative:", max_path_sum(TreeNode(-3, TreeNode(-2), TreeNode(-5)))[0])
print("single negative node:", max_path_sum(TreeNode(-7))[0])
print("negative child dropped:", max_path_sum(TreeNode(5, TreeNode(-8), TreeNode(2)))[0])
print("a chain of three:", max_path_sum(TreeNode(1, None, TreeNode(2, None, TreeNode(3))))[0])
trap = TreeNode(-5, TreeNode(10, TreeNode(20), TreeNode(30)), TreeNode(1))
print("best path below the root:", max_path_sum(trap)[0])

The chain row sums to 6, the whole chain. A path may run along one side only, and the upward gains carry it. Forgetting to clamp a child gain at zero is the pitfall; the -8 child would drag the root's offer from 7 down if it were kept.