Binary Tree Maximum Path Sum — Complete Walkthrough

If someone asks you to name the single hardest tree problem that still shows up regularly in interviews, the answer is almost always LeetCode #124: Binary Tree Maximum Path Sum. It is tagged Hard for good reason — the solution requires a recursive insight that most candidates struggle to see on their own.

The binary tree maximum path sum problem appears consistently at Google, Amazon, Meta, and Microsoft. Unlike simpler tree problems where the recursive return value is exactly what you need, this problem forces you to think about two different quantities simultaneously: what your function returns to its caller and what it tracks as the global answer.

In this walkthrough, you will build the complete solution from the ground up. By the end, you will understand the dual-recursion pattern that makes this problem solvable — and you will recognize it instantly when it appears in other Hard tree problems.

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes has an edge connecting them. The path does not need to pass through the root, and it does not need to go from a leaf to a leaf. It can start and end at any node in the tree.

Your task is to find the path with the largest sum of node values. The path must contain at least one node. Node values can be negative, which is where the real complexity hides.

Consider a tree where the root is 10, the left child is 2, and the right child is 10 with a right child of -25 that has children 3 and 4. The maximum path sum is 22, following the path 2 -> 10 -> 10. Notice how the path avoids the -25 subtree entirely — that is the key challenge the algorithm must handle.

The critical constraint is that a path cannot branch. It must be a single chain of nodes. This means if a path goes through a node, it can extend into at most one child on each side. It cannot fork into both children of one subtree.

Here is where most candidates get stuck. When you are at a node during recursion, there are two fundamentally different questions you need to answer. First, what is the maximum sum path that passes through this node? Second, what is the maximum single-branch contribution this node can offer to its parent?

These are not the same thing. The full path through a node can use both the left and right children: left_gain + node.val + right_gain. But the value you return to the parent can only include one branch, because the parent needs to extend the path in one direction — it cannot fork.

Think of it this way. When you report upward to your parent, you are saying: here is the best single chain from me downward that you can extend. But while you are at the current node, you also check whether left + me + right happens to be the best complete path you have seen so far.

This is the dual-recursion pattern. Your recursive function returns one thing (the single-branch max gain) but tracks another thing (the global best full path). Two different values, one function, one pass through the tree.

The algorithm performs a post-order DFS traversal. At each node, it computes the maximum gain from the left subtree and the right subtree. If either gain is negative, it is clamped to zero — you are better off not including that branch at all.

At each node, you compute the full path sum: left_gain + node.val + right_gain. This represents the best path that passes through the current node using both sides. You compare this against your global maximum and update if it is larger.

Then you return the single-branch gain: node.val + max(left_gain, right_gain). This is what the parent will use, because the parent can only extend the path through one of its children.

The entire algorithm runs in O(n) time and O(h) space, where h is the height of the tree. You visit each node exactly once, and the recursion stack is bounded by the tree height.

The difficulty of this hard tree problem comes down to one thing: the value your function returns is not the value it tracks. In almost every other tree recursion problem, the return value is the answer. Here, the return value is a helper quantity, and the real answer accumulates in a separate variable.

This confuses candidates because they try to make the recursion return the path sum directly. But that approach cannot work — the path sum through a node uses both children, while the return value to the parent can only use one child. If you try to return the full path, the parent will double-count branches.

Another source of confusion is the clamping to zero. Many candidates forget that you can simply skip a subtree if its gain is negative. The path does not have to include both children. It does not even have to include either child — a single node by itself is a valid path.

Once you see the pattern, the code is surprisingly short. The conceptual leap is the hard part. The implementation is about ten lines. This gap between difficulty of insight and simplicity of code is what makes LeetCode 124 such a favorite interview question.

The sneakiest edge case is a tree where every node value is negative. When all values are negative, the answer is the single largest (least negative) node. Your algorithm handles this correctly if you initialize maxSum to negative infinity and always consider the full path at every node, even when both gains are clamped to zero.

A single-node tree is the simplest case. The max path sum is just that node value. Your base case of returning 0 for null nodes means the single node will correctly compute 0 + node.val + 0 as the full path and return node.val as the single-branch gain.

A linear tree (every node has only one child) is essentially a linked list. The algorithm still works because one of the two gains will always be zero. The full path through any node becomes either left_gain + node.val or node.val + right_gain, and the global max tracks the best contiguous subarray — just like Kadane's algorithm applied to a tree.

These edge cases are what interviewers probe for. They want to see that your solution is robust, not just correct on balanced trees with positive values. Make sure you test with [-3], [-1, -2, -3], and a skewed tree like [1, 2, 3, null, null, null, 4].

Binary Tree Maximum Path Sum is not just a problem — it is a pattern. The "return one thing, track another" approach appears in several other Hard tree problems. Once you internalize it, you will recognize it immediately in problems like LeetCode #543 (Diameter of Binary Tree), #687 (Longest Univalue Path), and #1372 (Longest ZigZag Path).

The pattern works whenever the optimal answer at a node uses information from both subtrees, but the value passed upward to the parent can only include one subtree. Whenever you see that asymmetry, reach for this dual-recursion pattern.

The tree path recursion strategy is elegant because it solves the problem in a single O(n) pass. No second traversal, no memoization table, no complicated state. Just one DFS that returns a helper value and updates a global tracker.

If you are preparing for coding interviews, this is one of those problems worth drilling until the insight is automatic. YeetCode flashcards help you build that instant recall — flip the card, see "Binary Tree Max Path Sum," and immediately think: return single-branch gain, track left + node + right globally. That kind of pattern recognition is what separates candidates who solve Hard problems in 20 minutes from those who never find the approach.