The Unique Insight Behind the Binary Tree Maximum Path Sum (LeetCode 124)

Some coding interview problems feel routine… and then there are the ones that make you pause, sketch ideas, rethink your assumptions, and finally smile when the solution clicks.

For me, Binary Tree Maximum Path Sum was exactly that kind of problem.

It’s elegant.
It’s tricky at first glance.
And it teaches a powerful pattern used in many advanced tree problems.

If you're preparing for interviews or simply enjoy algorithmic puzzles, this one is worth mastering — and here’s why.

Problem Link

LeetCode 124 — Binary Tree Maximum Path Sum

Why This Problem Stood Out to Me

Most tree problems ask you to compute something simple like height, depth, or sum. But this one forces you to think differently:

A valid path doesn’t have to start at the root

A path can end anywhere

A path can go left → root → right, but cannot split upward

Sometimes the best path doesn’t even include the root

This combination makes the problem feel like a puzzle with multiple layers.

The “Aha!” moment is when you realize:

Each node must return the best one-sided path upward… but we must also track the best two-sided path that might pass through it.

Once this idea settles in, the recursion becomes surprisingly clean.

Putting It All Together With Examples

Once you understand the idea of one-sided paths and two-sided paths, the problem becomes much more intuitive. Here are a few examples that illustrate exactly how the recursion behaves and why the algorithm works.

Example 1 — The Classic “V” Shape Path

      1
     / \
    2   3

At node 1:
Best path going upward:
max(2, 3) + 1 = 4

Best through this node:
2 + 1 + 3 = 6

Maximum Path Sum = 6

Example 2 — When Negatives Force Interesting Choices

       -10
       /  \
      9   20
         /  \
        15   7

15 → 20 → 7

At node 20:

• one-sided upward path: 20 + max(15, 7) = 35
• two-sided local path: 15 + 20 + 7 = 42 ← candidate answer

The global maximum becomes 42, even though the root is negative.

Example 3 — Best Path Doesn’t Always Linear

        5
       / \
     4    8
    /    / \
   11   13  4
  /  \       \
 7    2       1

7 → 11 → 4 → 5 → 8 → 13

Sum = 48

All Negative Values

     -8
     / \
   -3  -6
       / \
     -9  -2

Sum = -2

The Core Idea Behind the Solution

Once you look at enough examples, the entire problem boils down to just two questions at every node:

1. What is the best path I can send upward?

This must be one-sided (left → node or node → right).

one_sided = node.val + max(left_gain, right_gain)

But if a side is negative, we drop it:

left_gain = max(dfs(left), 0)
right_gain = max(dfs(right), 0)

1. What is the best path that passes through this node?

This is where both sides can be used:

two_sided = left_gain + node.val + right_gain

This value updates the global maximum — but we never return it upward.

That’s the whole trick.

Final Solution

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
public:
    int helper(TreeNode* root, int& maxVal) {
        if (!root) {
            return 0;
        }
        int leftPath = helper(root->left, maxVal);
        int rightPath = helper(root->right, maxVal);

        int pathVal = root->val + max(0, leftPath) + max(0, rightPath);
        maxVal = max(pathVal, maxVal);

        return root->val + max(max(0, leftPath), max(0, rightPath));
    }
    int maxPathSum(TreeNode* root) {
        if (root == NULL) {
            return 0;
        }
        int maxVal = INT_MIN;
        helper(root, maxVal);
        return maxVal;
    }
};