Binary Tree Maximum Path Sum

Master this topic with zero to advance depth.

Binary Tree Maximum Path Sum

Max path sum (duplicate entry).

Hard

Approach 1

Level I: Brute Force (Iterate all peak nodes)

Intuition

Every path has a 'peak' node (the highest node in the tree structure that belongs to the path). A brute force approach iterates through every node in the tree, treats it as the peak, and calculates the maximum possible path extending down its left and right subtrees.

Logic

For each node, calculate max_down(node.left) and max_down(node.right).
Potential path sum = node.val + max_down(node.left) + max_down(node.right).
Return the maximum across all nodes.

⏱ O(N^2) (Calling max_down for each node)💾 O(H) (Recursion depth)

Detailed Dry Run

At node 20: Left path 15, Right path 7. Path = 15+20+7 = 42. Repeat for all nodes.

java

public class Main {
    public int maxPathSum(TreeNode root) {
        if (root == null) return Integer.MIN_VALUE;
        int current = root.val + Math.max(0, maxDown(root.left)) + Math.max(0, maxDown(root.right));
        return Math.max(current, Math.max(maxPathSum(root.left), maxPathSum(root.right)));
    }
    private int maxDown(TreeNode node) {
        if (node == null) return 0;
        return node.val + Math.max(0, Math.max(maxDown(node.left), maxDown(node.right)));
    }
}

Approach 2

Level II: Recursive DFS (Return Pair)

Intuition

We can solve this problem by having our recursive function return multiple pieces of information: specifically, the maximum path sum found within the subtree so far, and the maximum gain that can be used by an ancestor. This avoids using a global or member variable to track the maximum path sum.

Logic

Return a pair {max_path_overall, max_gain_to_parent}.
max_gain_to_parent = node.val + max(0, left_gain, right_gain).
max_path_here = node.val + max(0, left_gain) + max(0, right_gain).
max_path_overall = max(max_path_here, left_max_overall, right_max_overall).

Complexity

Time: $O(N)$
Space: $O(H)$

⏱ O(N)💾 O(H)

Detailed Dry Run

At node 20: Left returns {15, 15}, Right returns {7, 7}. Max path overall = max(15, 7, 20+15+7) = 42. Gain to return = 20+15 = 35.

java

class Result { int maxOverall, maxGain; Result(int o, int g) {maxOverall=o; maxGain=g;} }
public class Main {
    public int maxPathSum(TreeNode root) {
        return helper(root).maxOverall;
    }
    private Result helper(TreeNode node) {
        if (node == null) return new Result(Integer.MIN_VALUE, 0);
        Result left = helper(node.left);
        Result right = helper(node.right);
        int leftGain = Math.max(left.maxGain, 0);
        int rightGain = Math.max(right.maxGain, 0);
        int currentMax = node.val + leftGain + rightGain;
        int maxOverall = Math.max(currentMax, Math.max(left.maxOverall, right.maxOverall));
        int maxGain = node.val + Math.max(leftGain, rightGain);
        return new Result(maxOverall, maxGain);
    }
}

Approach 3

Level III: Optimal (Single-Pass Recursion)

Intuition

Thought Process

We perform a Post-order DFS. For each node, we want to know two things:

The maximum path sum that passes through this node as the peak (Highest point of an arch).
The maximum "gain" this node can contribute to a path coming from its parent.

Gain Logic

gain = node.val + max(0, leftGain, rightGain) We discard negative gains because a path would be shorter if it simply didn't include that subtree.

Diagram

       -10
       /  \
      9    20
          /  \
         15   7

Gain(15) = 15, Gain(7) = 7
At 20: Max path = 15+7+20 = 42. Gain to return to -10 = 20+15 = 35.
At -10: Max path = 9+35-10 = 34. 
Result: 42.

⏱ O(N)💾 O(H)

Detailed Dry Run

Node	Left Gain	Right Gain	Node Sum	Global Max
15	0	0	15	15
7	0	0	7	15
20	15	7	42	42
9	0	0	9	42
-10	9	35	34	42

java

public class Main {
    private int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        helper(root);
        return max;
    }
    private int helper(TreeNode root) {
        if (root == null) return 0;
        int left = Math.max(helper(root.left), 0);
        int right = Math.max(helper(root.right), 0);
        max = Math.max(max, root.val + left + right);
        return root.val + Math.max(left, right);
    }
}

⚠️ Common Pitfalls & Tips

Negative values can be tricky. If all nodes are negative, the max path might just be the single node with the highest value (least negative). That's why we initialize max to Integer.MIN_VALUE and use Math.max(..., 0) to decide whether to include subtrees.

← Previous QuestionSerialize and Deserialize Binary Tree

Next Question →Recover Binary Search Tree

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.