Maximum Path Sum in Binary Tree in DSA Java

Mental Model

Find the highest sum of values along any path in a tree, where the path can start and end at any node.

Analogy: Imagine a mountain range where each peak has a height (value). You want to find the highest possible trail that can go up and down connecting any peaks, not necessarily starting at the base or ending at the top.

      1
     / \
    2   3
   / \   \
  4  -5   6

Dry Run Walkthrough

Input: Binary tree: 1 -> 2, 3; 2 -> 4, -5; 3 -> null, 6

Goal: Find the maximum sum of any path in the tree, where path can start and end anywhere

Step 1: Start at leaf node 4, max path sum from 4 is 4

Node 4: max path sum = 4

Why: Leaf nodes have max path sum equal to their own value

Step 2: At node -5, max path sum from -5 is -5

Node -5: max path sum = -5

Why: Negative leaf node max path sum is its own value

Step 3: At node 2, calculate max path sum including left and right children

Node 2: max path sum from left child 4 = 4, right child -5 = -5

Why: We consider only positive sums from children to maximize path

Step 4: At node 2, max single path = max(2, 2+4, 2+0) = 6; max path through node = 2 + 4 + 0 = 6

Node 2: max single path = 6, max path through node = 6

Why: Choose best path including node and one or both children

Step 5: At node 6, max path sum from 6 is 6

Node 6: max path sum = 6

Why: Leaf node max path sum is its own value

Step 6: At node 3, max single path = max(3, 3+6) = 9; max path through node = 9

Node 3: max single path = 9, max path through node = 9

Why: Include positive child path to maximize sum

Step 7: At root 1, max single path = max(1, 1+6, 1+9) = 10; max path through node = 1 + 6 + 9 = 16

Node 1: max single path = 10, max path through node = 16

Why: Max path can include both children and node itself

Result:

Maximum path sum = 16

Annotated Code

DSA Java

public class MaxPathSumBinaryTree {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    private int maxSum = Integer.MIN_VALUE;

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

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

        // max sum on the left and right sub-trees of node
        int leftGain = Math.max(maxGain(node.left), 0); // ignore negative paths
        int rightGain = Math.max(maxGain(node.right), 0);

        // price to start a new path where `node` is highest node
        int priceNewPath = node.val + leftGain + rightGain;

        // update maxSum if priceNewPath is better
        maxSum = Math.max(maxSum, priceNewPath);

        // for recursion: return max gain if continue the same path
        return node.val + Math.max(leftGain, rightGain);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(-5);
        root.right.right = new TreeNode(6);

        MaxPathSumBinaryTree solver = new MaxPathSumBinaryTree();
        System.out.println(solver.maxPathSum(root));
    }
}

if (node == null) return 0;

stop recursion at null nodes

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

calculate max gain from left child, ignore negative sums

int rightGain = Math.max(maxGain(node.right), 0);

calculate max gain from right child, ignore negative sums

int priceNewPath = node.val + leftGain + rightGain;

calculate max path sum with current node as root

maxSum = Math.max(maxSum, priceNewPath);

update global max if current path is better

return node.val + Math.max(leftGain, rightGain);

return max gain continuing from current node to parent

Output

16

Complexity Analysis

Time: O(n) because we visit each node once in the recursion

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Naive approach tries all paths explicitly with O(n^2) cost; this uses recursion to compute max gain efficiently

Edge Cases

Empty tree

Returns Integer.MIN_VALUE or 0 depending on implementation; here returns Integer.MIN_VALUE

DSA Java

if (node == null) return 0;

All negative values

Returns the largest single node value as max path sum

DSA Java

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

Single node tree

Returns the value of the single node

DSA Java

if (node == null) return 0;

When to Use This Pattern

When asked to find the maximum sum path in a tree that can start and end anywhere, use the max path sum pattern with recursion and global tracking.

Common Mistakes

Mistake: Not ignoring negative child sums, which lowers the max path sum
Fix: Use Math.max(childGain, 0) to ignore negative paths

Mistake: Returning the max path sum instead of max gain for recursion
Fix: Return max gain (node.val + max(leftGain, rightGain)) to parent, not max path sum

Summary

Finds the highest sum of values along any path in a binary tree.

Use when you need the max sum path that can start and end at any node.

The key is to track max gain from children ignoring negatives and update global max including both children.

Practice

1. What does the Maximum Path Sum in Binary Tree problem ask you to find?

easy

A. The highest sum of values along any path in the tree

B. The longest path length in the tree

C. The smallest value in the tree

D. The number of leaf nodes in the tree

Solution

1. Step 1: Understand the problem goal

   The problem asks for the maximum sum of node values along any path in the binary tree. A path can start and end at any node but must be connected.

2. Step 2: Differentiate from other tree metrics

   It is not about path length, smallest value, or leaf count. It focuses on sum of node values along a path.

3. Final Answer:

   The highest sum of values along any path in the tree -> Option A

4. Quick Check:

   Maximum path sum = highest sum of connected nodes [OK]

Hint: Focus on sum of node values, not path length or count [OK]

Common Mistakes:

• Confusing path sum with path length
• Thinking path must start at root
• Ignoring negative values in nodes

2. Which of the following Java method signatures is correct for a function that returns the maximum path sum in a binary tree node class TreeNode?

easy

A. public void maxPathSum(TreeNode root) int

B. public int maxPathSum(TreeNode root)

C. int maxPathSum(TreeNode root) void

D. maxPathSum(TreeNode root) -> int

Solution

1. Step 1: Recall Java method syntax

   In Java, a method returning an int with public access and a parameter of type TreeNode is declared as: public int maxPathSum(TreeNode root).

2. Step 2: Check other options for syntax errors

   Options A, B, and D have invalid syntax: missing return type, misplaced void, or arrow notation not used in Java.

3. Final Answer:

   public int maxPathSum(TreeNode root) -> Option B

4. Quick Check:

   Java method syntax = public int methodName(Type param) [OK]

Hint: Remember Java method syntax: access returnType name(params) [OK]

Common Mistakes:

• Using arrow notation like other languages
• Mixing return type and void incorrectly
• Omitting access modifier

3. Given the following binary tree:

    1
   / \
  2   3

What is the maximum path sum?

medium

A. 4

B. 5

C. 3

D. 6

Solution

1. Step 1: Identify all possible paths and their sums

   Paths and sums: 2 alone = 2, 3 alone = 3, 1 alone = 1, 2->1 = 3, 3->1 = 4, 2->1->3 = 6.

2. Step 2: Find the maximum sum

   The maximum sum is 6 from path 2->1->3.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   Sum(2+1+3) = 6 [OK]

Hint: Check sums including root and both children [OK]

Common Mistakes:

• Ignoring paths that go through root connecting both children
• Only considering single branches
• Adding node values incorrectly

4. Consider this Java method snippet for maximum path sum:

int maxPathSum(TreeNode root) {
  if (root == null) return 0;
  int left = maxPathSum(root.left);
  int right = maxPathSum(root.right);
  return Math.max(left, right) + root.val;
}

What is the main issue with this code?

medium

A. It uses Math.max instead of Math.min

B. It returns 0 for null nodes instead of Integer.MIN_VALUE

C. It does not consider paths passing through the root connecting left and right

D. It does not handle negative node values

Solution

1. Step 1: Analyze the recursive return value

   The code returns the max sum of either left or right subtree plus root value, ignoring the case where path passes through root connecting both sides.

2. Step 2: Understand maximum path sum definition

   Maximum path sum can include left subtree + root + right subtree, which this code misses.

3. Final Answer:

   It does not consider paths passing through the root connecting left and right -> Option C

4. Quick Check:

   Missing combined path sum through root [OK]

Hint: Remember max path can include both left and right subtrees [OK]

Common Mistakes:

• Ignoring combined paths through root
• Assuming max of left/right is enough
• Not updating global max path sum

5. You have a binary tree with nodes that can have negative values. Which approach correctly finds the maximum path sum?

hard

A. Use a recursive helper that returns max gain from each node, update global max with max of left + node + right, and ignore negative gains by comparing with 0

B. Sum all node values and return the total as maximum path sum

C. Only consider paths starting from root to leaf nodes

D. Use breadth-first search to find the longest path and sum its nodes

Solution

1. Step 1: Understand handling negative values

   Negative node values can reduce path sum, so ignore negative gains by comparing with 0 when calculating max gain from children.

2. Step 2: Use recursive helper with global max update

   Recursively compute max gain from left and right, update global max with left + node + right, and return max gain for parent calls.

3. Step 3: Reject incorrect approaches

   Summing all nodes ignores path constraints, root-to-leaf only misses other paths, BFS longest path ignores sums.

4. Final Answer:

   Use a recursive helper that returns max gain from each node, update global max with max of left + node + right, and ignore negative gains by comparing with 0 -> Option A

5. Quick Check:

   Recursive max gain + global max update handles negatives [OK]

Hint: Ignore negative gains by max(child, 0) in recursion [OK]

Common Mistakes:

• Summing all nodes regardless of path
• Only considering root-to-leaf paths
• Not handling negative values properly