Binary Tree Maximum Path Sum

This one trips up a lot of people. The tree has values. You want the path with the biggest total. Sounds easy. The hard part is one tiny idea: a node can be the top of a path, or a node can be a step inside a bigger path. Telling those two cases apart is the whole question. Once you see it, the code is short.

🎯 The Problem

You get a binary tree where each node holds a number. Return the biggest total any path can reach.

The rules:

• Each node holds a number, and the number can be negative.
• A path is any chain of connected nodes where you never visit a node twice.
• The path does not need to touch the root.
• It does not even need to reach a leaf.
• You add up the values along the path. You want the largest such total.

Let us use a small tree. The root is -10. Its left child is 9. Its right child is 20. The 20 has children 15 and 7.

Input (the tree):
       -10
       /  \
      9    20
          /  \
         15    7

Output: 42

Explanation: The best path is 15 -> 20 -> 7.
That gives 15 + 20 + 7 = 42. The root -10 only hurts the total, so we skip it.

Notice the best path here does not pass through the root at all. The path bends at the node 20. It comes up from 15, passes the 20, and goes down to 7.

Here is the tree, so you can picture where that winning path sits.

🐢 Approach 1: Try Every Path (Brute Force)

The idea in one line: list every possible path, add each one up, and keep the biggest total.

The idea:

• For each node, start a search that walks outward in every direction.
• Add up the values along each path.
• Keep the largest total you ever see.

Why it is weak:

• A tree can have a huge number of paths.
• You re-walk the same nodes again and again from different starting points.
• The work climbs toward O(n²) or worse on a long chain.

Here is the DFS-gain code:

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

⚡ Approach 2: Gain Versus Through-Node (Best)

The idea in one line: at each node, answer two different questions in one walk, and never mix them up.

The two questions:

• The gain: the best total you can carry up through this node to its parent.
• The through-node total: the best path that bends at this node.

Why the gain uses one branch:

• A path going up to the parent can use only one child branch, not both.
• If it used both, it would come back down through the node and could not continue up.
• So the gain is the node’s value plus the better of its two children’s gains.

Why the through-node total uses both branches:

• It comes up the left branch, passes the node, and goes down the right branch.
• It uses both children, so it cannot continue up to the parent.
• It is a finished path. Compare it against the best answer so far.

How it works:

• At every node, compute both values.
• Return the gain to the parent. Update a running best with the through-node total.
• One walk over the tree does it all.
• If a child’s gain is negative, treat it as zero. A negative branch only shrinks the total.

Why it is fast:

• Each node is visited once with a little constant work.
• That is O(n) time.

Here is the dry run at node 20, where the best path forms.

Steps to Solve

1. Keep one running variable for the best path total found so far. Start it very low.
2. Write a recursive helper that returns the gain of a node.
3. For a missing node, the gain is zero.
4. Ask each child for its gain. If a child’s gain is negative, replace it with zero.
5. Compute the through-node total as the node’s value plus the left gain plus the right gain.
6. Update the best answer with that through-node total.
7. Return the gain upward, which is the node’s value plus the larger of the two child gains.
8. After the walk finishes, the best variable holds the answer.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef struct Node {
    int val;
    struct Node *left, *right;
} Node;

Node *newNode(int v) {
    Node *n = malloc(sizeof(Node));
    n->val = v;
    n->left = n->right = NULL;
    return n;
}

int best;  // running best path total

int maxx(int a, int b) { return a > b ? a : b; }

int gain(Node *node) {
    if (!node) return 0;                 // missing node adds nothing
    int left = maxx(gain(node->left), 0);   // drop negative branches
    int right = maxx(gain(node->right), 0);
    int through = node->val + left + right; // path that bends here
    if (through > best) best = through;     // update answer
    return node->val + maxx(left, right);   // gain to carry upward
}

int main(void) {
    Node *root = newNode(-10);
    root->left = newNode(9);
    root->right = newNode(20);
    root->right->left = newNode(15);
    root->right->right = newNode(7);

    best = INT_MIN;
    gain(root);
    printf("%d\n", best);
    return 0;
}

42

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

struct Node {
    int val;
    Node *left, *right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

int gain(Node *node, int &best) {
    if (!node) return 0;                       // missing node adds nothing
    int left = max(gain(node->left, best), 0);   // drop negative branches
    int right = max(gain(node->right, best), 0);
    int through = node->val + left + right;      // path that bends here
    best = max(best, through);                   // update answer
    return node->val + max(left, right);         // gain to carry upward
}

int main() {
    Node *root = new Node(-10);
    root->left = new Node(9);
    root->right = new Node(20);
    root->right->left = new Node(15);
    root->right->right = new Node(7);

    int best = INT_MIN;
    gain(root, best);
    cout << best << endl;
    return 0;
}

42

public class MaxPathSum {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
    }

    static int best = Integer.MIN_VALUE;  // running best path total

    static int gain(Node node) {
        if (node == null) return 0;                 // missing node adds nothing
        int left = Math.max(gain(node.left), 0);    // drop negative branches
        int right = Math.max(gain(node.right), 0);
        int through = node.val + left + right;       // path that bends here
        best = Math.max(best, through);              // update answer
        return node.val + Math.max(left, right);     // gain to carry upward
    }

    public static void main(String[] args) {
        Node root = new Node(-10);
        root.left = new Node(9);
        root.right = new Node(20);
        root.right.left = new Node(15);
        root.right.right = new Node(7);

        gain(root);
        System.out.println(best);
    }
}

42

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


def max_path_sum(root):
    best = [float("-inf")]  # running best path total

    def gain(node):
        if not node:                       # missing node adds nothing
            return 0
        left = max(gain(node.left), 0)     # drop negative branches
        right = max(gain(node.right), 0)
        through = node.val + left + right  # path that bends here
        best[0] = max(best[0], through)    # update the answer
        return node.val + max(left, right) # gain to carry upward

    gain(root)
    return best[0]


root = Node(-10)
root.left = Node(9)
root.right = Node(20)
root.right.left = Node(15)
root.right.right = Node(7)

print(max_path_sum(root))

42

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function maxPathSum(root) {
  let best = -Infinity; // running best path total

  function gain(node) {
    if (!node) return 0;                        // missing node adds nothing
    const left = Math.max(gain(node.left), 0);  // drop negative branches
    const right = Math.max(gain(node.right), 0);
    const through = node.val + left + right;    // path that bends here
    best = Math.max(best, through);             // update the answer
    return node.val + Math.max(left, right);    // gain to carry upward
  }

  gain(root);
  return best;
}

const root = new Node(-10);
root.left = new Node(9);
root.right = new Node(20);
root.right.left = new Node(15);
root.right.right = new Node(7);

console.log(maxPathSum(root));

42

Let us walk through the Python version line by line, because the two-questions idea lives in these few lines.

The line best = [float("-inf")] is the running answer. We start it as the smallest possible value. We wrap it in a list so the inner function can change it. A negative answer is allowed, since values can be negative.

Inside gain, the line if not node: return 0 handles a missing child. A missing branch contributes nothing. So its gain is zero.

The line left = max(gain(node.left), 0) asks the left child for its gain. Then it clamps the result at zero. This is the negative-branch rule. If using that branch would lower the total, we drop it and treat it as zero. The same happens for right.

The line through = node.val + left + right is the through-node total. This is the path that bends at this node, using both children. It is a finished path. It cannot continue up to the parent.

The line best[0] = max(best[0], through) checks if this bending path beats our best so far. This is the only place we record an answer. So every node gets a chance to be the top of the best path.

The last line return node.val + max(left, right) is the gain we hand to the parent. Here we keep only the better child, not both. A path going up to the parent can use just one branch. That is the difference between the value we return and the value we compare.

⏱️ Time and Space Complexity

The slow way re-walks paths from many starting points, so it climbs toward O(n²). The optimal way visits each node once and does a little constant work there. So it is O(n) time. The space is O(h), where h is the height of the tree, because the recursion stack goes as deep as the tree is tall.

🧩 Key Takeaways

• ✅ Each node answers two questions: the gain to carry up, and the best path that bends here.
• ✅ The gain uses only one child branch, because a path going to the parent cannot use both.
• ✅ The through-node total uses both children, and it is a finished path we compare to the answer.
• ✅ Clamp any negative child gain to zero, since a negative branch only shrinks the total.
• ✅ One post-order walk solves it in O(n) time.

🚀 What’s Next?

• Construct Binary Tree from Preorder and Inorder Traversal
• Serialize and Deserialize Binary Tree