🌳 LeetCode 124: Binary Tree Maximum Path Sum – A Complete Guide with Intuition and Java Solution

Difficulty: Hard

Topics: Binary Tree, Depth-First Search (DFS), Recursion, Dynamic Programming on Trees

🚀 Introduction

Binary Trees are one of the most fascinating and frequently asked data structures in technical interviews. Among them, LeetCode Problem 124: Binary Tree Maximum Path Sum is a beautiful combination of recursion, tree traversal, and optimization.

In this post, we’ll:

Break down the problem statement
Understand the intuitive approach
Deep dive into the Java solution
Walk through example cases step-by-step
Discuss some practical insights and edge cases

📚 Problem Statement

You are given a binary tree, and you need to find the path with the maximum sum.

The Rules:

A path is a sequence of nodes where each pair of adjacent nodes has a parent-child relationship.
The path does not need to pass through the root.
The path must contain at least one node.
The path can start and end anywhere in the tree.

Your task:

Return the maximum sum obtainable from any such path.

🧮 Example 1:

        1
       / \
      2   3

Output: 6

👉 Explanation: The maximum path is 2 -> 1 -> 3 with a sum of 6.

🧮 Example 2:

Output: 42

👉 Explanation: The maximum path is 15 -> 20 -> 7 with a sum of 42.

🔒 Constraints

The number of nodes: 1 to 30,000
Node values: -1000 to 1000

🧩 Key Concepts to Understand

1. Path Sum Through a Node

For each node, there are two key things to consider:

Maximum sum that can be extended to the parent node

(This can only come from one side: either the left or the right subtree.)
Maximum path sum passing through the current node

(This can include both left and right subtrees.)

2. Global Maximum vs. Local Path

Each node contributes to a local path sum.
The global maximum path sum should be updated if the local path at the current node exceeds the previously recorded maximum.

🧠 Intuition and Approach

We can use a post-order traversal (left → right → node) because:

We need to compute the maximum path sum from the bottom up.
Each node’s answer depends on its children.

Algorithm Steps:

Traverse to the bottom of the tree using recursion.
Calculate the maximum gain from the left and right subtrees.
Ignore negative paths because they decrease the total sum. (Math.max(leftGain, 0) ensures this)
Calculate the maximum path sum passing through the current node.
Update the global maximum sum if this local path is greater.
Return the maximum gain to contribute to the parent.

💻 Java Solution

class Solution {
    private int maxSum = Integer.MIN_VALUE; // Global maximum path sum

    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    private int maxGain(TreeNode node) {
        if (node == null) return 0;

        // Calculate maximum gain from left and right children
        int leftGain = Math.max(maxGain(node.left), 0); // Ignore negative paths
        int rightGain = Math.max(maxGain(node.right), 0);

        // Path sum including both left and right children
        int currentMaxPath = node.val + leftGain + rightGain;

        // Update global maximum if current path is better
        maxSum = Math.max(maxSum, currentMaxPath);

        // Return maximum gain to the parent
        return node.val + Math.max(leftGain, rightGain);
    }
}

🌟 Step-by-Step Example
Let’s dry-run Example 2:

Input Tree:
      -10
      /  \
     9   20
         / \
        15  7

🛠️ Traversal and Computation:

Visit node 9 → max gain: 9

Visit node 15 → max gain: 15

Visit node 7 → max gain: 7

Visit node 20 → left gain: 15, right gain: 7 → max path through 20: 15 + 20 + 7 = 42

Visit root -10 → left gain: 9, right gain: 35 → max path through root: 9 + (-10) + 35 = 34

✅ Global max path sum: 42

❌ Why Do We Ignore Negative Paths?

If the path sum of a subtree is negative, adding it to the parent will decrease the total sum.

That’s why we do:

int leftGain = Math.max(maxGain(node.left), 0);

🌱 Additional Tips

Time Complexity: O(N), since we visit each node once.
Space Complexity: O(H), where H is the height of the tree (due to the recursion stack).

🚩 Common Pitfalls:

❗ Forgetting to track the global maximum.
❗ Forgetting to return the correct gain to the parent (you can’t return both children’s gains because paths cannot split).

✨ Summary

This problem beautifully combines tree traversal with dynamic thinking.

Understanding when to split paths and when to choose one child is the core of solving it.

Here’s what we’ve learned:

How to use post-order DFS to solve tree-based DP problems.
How to correctly update global results from local computations.
Why ignoring negative paths is essential.

❤️ Connect & Share!

If you found this explanation helpful, consider sharing it with your fellow developers.

Let’s grow and learn together! 🌱

You can also follow me for more posts on:

Data Structures & Algorithms
LeetCode Problem Guides
Java and Backend Development

DEV Community