LogoKode$word

LeetCode 124: Binary Tree Maximum Path Sum – Java DFS Solution Explained

Learn how to solve LeetCode 124 Binary Tree Maximum Path Sum using optimized DFS recursion in Java. Includes intuition, brute force approach, optimized solution, dry run, complexity analysis, interview explanation, and common mistakes.

Krishna Shrivastava
1 views
LinkedInGithubX
0
0
LeetCodeBinary Tree Maximum Path SumJavaBinary TreeDFSTreeRecursionDynamic Programming on TreesHard
LeetCode 124: Binary Tree Maximum Path Sum – Java DFS Solution Explained
Listen to articleAudio version
Ad
Advertisement

Introduction

LeetCode 124 – Binary Tree Maximum Path Sum is one of the most important and frequently asked hard-level binary tree interview problems.

This problem teaches:

  1. Depth First Search (DFS)
  2. Bottom-up recursion
  3. Tree Dynamic Programming
  4. Recursive optimization
  5. Global answer tracking

It is considered a classic interview problem because it combines:

  1. Tree traversal
  2. Recursive decision making
  3. Path optimization
  4. Negative value handling

Mastering this problem helps in understanding advanced binary tree patterns used in:

  1. Diameter problems
  2. Tree DP
  3. Maximum path problems
  4. Graph recursion problems

Problem Link

🔗 https://leetcode.com/problems/binary-tree-maximum-path-sum/

Problem Statement

Given the root of a binary tree:

Return:

Maximum path sum of any non-empty path

A path:

  1. Can start from any node
  2. Can end at any node
  3. Must follow parent-child connections
  4. Cannot visit a node more than once

Important:

Path does NOT need to pass through root

Example 1

Input

root = [1,2,3]

Tree:

1
/ \
2 3

Output

6

Explanation:

Best path:

2 → 1 → 3

Path sum:

2 + 1 + 3 = 6

Example 2

Input

root = [-10,9,20,null,null,15,7]

Tree:

-10
/ \
9 20
/ \
15 7

Output

42

Explanation:

Best path:

15 → 20 → 7

Sum:

15 + 20 + 7 = 42

Key Observation

At every node:

We have two important possibilities.

Possibility 1

Path continues upward to parent.

In this case:

We can choose only:

ONE side

because path cannot split upward.

Return value becomes:

node + max(left, right)

Possibility 2

Current node becomes:

Highest point of path

Then we can use:

left + node + right

This candidate updates global maximum answer.

Core Recursive Idea

At every node:

  1. Calculate left maximum contribution
  2. Calculate right maximum contribution
  3. Ignore negative paths
  4. Update global answer
  5. Return best single-side path upward

Why Ignore Negative Paths?

Negative paths reduce total sum.

So:

Math.max(path, 0)

ensures:

  1. Negative contribution is discarded
  2. Only profitable paths are considered

This is the most important optimization.

Your Java Solution

class Solution {

int max = Integer.MIN_VALUE;

public int solve(TreeNode roo) {

if(roo == null)
return 0;

int left = Math.max(solve(roo.left), 0);

int right = Math.max(solve(roo.right), 0);

max = Math.max(max, roo.val + left + right);

return roo.val + Math.max(left, right);
}

public int maxPathSum(TreeNode root) {

solve(root);

return max;
}
}

Why This Works

For every node:

We calculate:

Best path passing through current node

which is:

left + node + right

This path may become global maximum.

But while returning upward:

We can only choose:

one direction

because paths cannot split.

Dry Run

Input

-10
/ \
9 20
/ \
15 7

Step 1

Leaf nodes:

9 → return 9
15 → return 15
7 → return 7

Step 2

At node:

20

Left:

15

Right:

7

Current best path:

15 + 20 + 7 = 42

Update:

max = 42

Return upward:

20 + max(15,7)
= 35

Step 3

At node:

-10

Left:

9

Right:

35

Candidate:

9 + (-10) + 35 = 34

Global maximum remains:

42

Final Answer

42

Recursive Visualization

solve(-10)
├── solve(9)
│
└── solve(20)
├── solve(15)
└── solve(7)

Global maximum gets updated during return phase.

Brute Force Approach

A brute force approach would:

  1. Generate all possible paths
  2. Calculate sums
  3. Track maximum

But number of paths becomes extremely large.

This is inefficient.

Brute Force Complexity

Time Complexity

Can become:

O(N²)

or worse depending on implementation.

Optimized DFS Complexity

Time Complexity

O(N)

because every node is visited once.

Space Complexity

O(H)

where:

H = height of tree

Worst case:

O(N)

for skewed tree.

Important Insight

Two values exist at every node.

1. Value Returned Upward

Only one side allowed:

node + max(left, right)

2. Value Used for Global Maximum

Both sides allowed:

left + node + right

This distinction is the heart of the problem.

Interview Explanation

In interviews, explain:

Every node acts as a potential highest point of a path. We compute the best path through that node while recursively returning the best single-side contribution upward.

This demonstrates:

  1. Advanced DFS understanding
  2. Tree DP concepts
  3. Recursive optimization
  4. Handling negative paths

Common Mistakes

1. Returning Both Sides Upward

Incorrect:

left + node + right

A path cannot branch upward.

2. Forgetting Negative Path Handling

Always use:

Math.max(value, 0)

3. Assuming Path Must Pass Root

The path can exist entirely inside a subtree.

4. Not Using Global Variable

Maximum path may occur anywhere.

FAQs

Q1. Does path need to start from root?

No.

It can start and end anywhere.

Q2. Why ignore negative sums?

Negative paths reduce overall answer.

Q3. Why can we return only one side?

Because a path moving upward cannot split into two directions.

Q4. Is this problem important for interviews?

Extremely important.

It is one of the most famous hard-level tree problems.

Related Problems

After mastering this problem, practice:

  1. Diameter of Binary Tree
  2. Balanced Binary Tree
  3. Maximum Depth of Binary Tree

Conclusion

LeetCode 124 is one of the best problems for learning advanced binary tree recursion.

It teaches:

  1. DFS optimization
  2. Tree dynamic programming
  3. Recursive decision making
  4. Negative path handling
  5. Global answer tracking

The key insight is:

Every node can become the highest point of a maximum path.

Once this recursive pattern becomes clear, many advanced tree and graph problems become much easier to solve.

Related Articles

LeetCode 104: Maximum Depth of Binary Tree – Java Recursive Solution Explained

LeetCode 104: Maximum Depth of Binary Tree – Java Recursive Solution Explained

Learn how to solve LeetCode 104 Maximum Depth of Binary Tree using recursion and DFS in Java. Includes brute force intuition, optimized recursive approach, BFS solution, dry run, complexity analysis, interview explanation, and common mistakes.

Read Article
LeetCode 110: Balanced Binary Tree – Java Optimized DFS Solution Explained

LeetCode 110: Balanced Binary Tree – Java Optimized DFS Solution Explained

Learn how to solve LeetCode 110 Balanced Binary Tree using optimized DFS and height calculation in Java. Includes brute force approach, optimized recursive solution, intuition, dry run, complexity analysis, interview explanation, and common mistakes.

Read Article
LeetCode 94: Binary Tree Inorder Traversal – Java Recursive & Iterative Solution Explained

LeetCode 94: Binary Tree Inorder Traversal – Java Recursive & Iterative Solution Explained

Learn how to solve LeetCode 94 Binary Tree Inorder Traversal using Recursive and Iterative approaches in Java. Includes tree traversal intuition, dry run, stack-based solution, complexity analysis, interview tips, and common mistakes.

Read Article
LeetCode 543: Diameter of Binary Tree – Java DFS Solution Explained

LeetCode 543: Diameter of Binary Tree – Java DFS Solution Explained

Learn how to solve LeetCode 543 Diameter of Binary Tree using optimized DFS recursion in Java. Includes brute force approach, optimized solution, intuition, dry run, complexity analysis, interview explanation, and common mistakes.

Read Article
Ai Assistant Kas