MANG Problem #9: Binary Tree Maximum Path Sum (Hard)

1. Problem Statement

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.

2. Approach: Post-Order DFS with Global Max

graph TD
    Node((Current Node))
    Left[Left Gain]
    Right[Right Gain]
    
    Node --> Left
    Node --> Right
    
    Path[Full Path: L + Node + R]
    Return[Return to Parent: Node + max(L, R)]
    
    Node -.-> Path
    Node -.-> Return

The trick to this problem is understanding that at any given node, it can be:

The "Middle" of a path: The path comes from the left child, goes through the node, and down to the right child.
Part of a path going up: The path comes from one child, goes through the node, and continues to its parent.
Recursion: We use a function maxGain(node) that returns the maximum sum a path can get from this node and one of its subtrees.
Global Update: Inside the function, we calculate the price of a "new" path that uses both children: node.val + leftGain + rightGain. We update a global maxSum with this value.
Gain: We return node.val + max(leftGain, rightGain) to the parent.

3. Java Implementation

class Solution {
    int maxSum = Integer.MIN_VALUE;

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

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

        // 1. Calculate max sum from subtrees. Ignore negative gains.
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);

        // 2. The path that "turns" at this node
        int currentPathSum = node.val + leftGain + rightGain;

        // 3. Update global maximum
        maxSum = Math.max(maxSum, currentPathSum);

        // 4. For the parent, we can only pick ONE subtree branch
        return node.val + Math.max(leftGain, rightGain);
    }
}

4. 5-Minute "Video-Style" Walkthrough

The "Aha!" Moment: A path is like a string of pearls. You can pick it up from the middle. Every node in the tree is a potential "peak" of a path.
Handling Negatives: If a subtree returns a negative sum, we treat it as 0. Why? Because we'd rather not include that subtree at all if it's going to decrease our total sum.
The Two Roles: Every node plays two roles. It helps its parent find a path, but it also checks if it's the "highest point" of its own independent path.

5. Interview Discussion

Interviewer: "What is the time complexity?"
You: "O(N) because we visit each node exactly once during our DFS traversal."
Interviewer: "Space complexity?"
You: "O(H) where H is the tree height, for the recursion stack. In a balanced tree, that's O(log N); in a skewed tree, it's O(N)."