14. Binary Tree Maximum Path Sum

Description

Binary Tree Maximum Path Sum

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node’s values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.

Example 1:

Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

Example 2:

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

Constraints:

• The number of nodes in the tree is in the range [1, 3 * 104].
• -1000 <= Node.val <= 1000

Approach - DFS

• There are three possible answer after we compute left and right, one is left + current + right other is left + current and right + current
• Time: O(n) Space: O(h)

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

Approach 1: Bottom-Up Recursive DFS ($O(N)$ Time, $O(H)$ Space)

Intuition

To find the maximum path sum, treat each node as the potential top-most turning point of a path:

1. Recursively calculate the maximum path sum contributed by the left and right subtrees (maxGain).
2. If a subtree returns a negative gain, discard it by taking Math.max(0, gain).
3. The total path sum centered at the current node is node.val + leftGain + rightGain. Update the global maximum path sum maxSum.
4. Return node.val + Math.max(leftGain, rightGain) back to the parent caller, as a path going up to a parent can only extend down one branch (left or right, not both).

class Solution {
    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;
 
        // Ignore negative path gains by clamping to 0
        int leftGain = Math.max(0, maxGain(node.left));
        int rightGain = Math.max(0, maxGain(node.right));
 
        // Path sum centered at the current node (turning point)
        int currentPathSum = node.val + leftGain + rightGain;
        maxSum = Math.max(maxSum, currentPathSum);
 
        // Return maximum single-branch gain extending upward to parent
        return node.val + Math.max(leftGain, rightGain);
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Every node is visited exactly once.
• Space Complexity: $O(H)$ — Recursion stack size is bounded by the height of the tree $H$ ($O(\log N)$ for balanced trees, $O(N)$ for skewed trees).

---

Approach 2: Iterative Postorder Traversal ($O(N)$ Time, $O(N)$ Space)

Intuition

Simulate the bottom-up recursion iteratively using a single-stack postorder traversal (ArrayDeque + lastVisited pointer) along with a Map<TreeNode, Integer> to store each node’s maximum single-branch gain:

1. Traverse left down to leaf nodes, pushing nodes onto the stack.
2. Peek the stack top (peekNode). If its right subtree is non-null and unvisited, switch to curr = peekNode.right.
3. Otherwise, pop peekNode and fetch its children’s gains from maxGains (clamped to 0).
4. Update global maxSum with peekNode.val + leftGain + rightGain.
5. Store peekNode.val + Math.max(leftGain, rightGain) into maxGains for its parent node to use.

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;
 
class Solution {
    public int maxPathSum(TreeNode root) {
        int maxSum = Integer.MIN_VALUE;
        Deque<TreeNode> stack = new ArrayDeque<>();
        Map<TreeNode, Integer> maxGains = new HashMap<>();
 
        TreeNode curr = root;
        TreeNode lastVisited = null;
 
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
 
            TreeNode peekNode = stack.peek();
            if (peekNode.right != null && lastVisited != peekNode.right) {
                curr = peekNode.right;
            } else {
                stack.pop();
 
                int leftGain = Math.max(0, maxGains.getOrDefault(peekNode.left, 0));
                int rightGain = Math.max(0, maxGains.getOrDefault(peekNode.right, 0));
 
                // Path sum where peekNode is the turning point
                int currentPathSum = peekNode.val + leftGain + rightGain;
                maxSum = Math.max(maxSum, currentPathSum);
 
                // Store max single-branch gain for parent calculations
                maxGains.put(peekNode, peekNode.val + Math.max(leftGain, rightGain));
                lastVisited = peekNode;
            }
        }
 
        return maxSum;
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Each node is pushed, popped, and processed once.
• Space Complexity: $O(N)$ — Requires stack space and map storage for all node gains.

---

Easy Memory Rule

“At each node: Curved path sum = val + max(0, left) + max(0, right) $\to$ Return straight branch val + max(0, max(left, right))!”