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

1. Problem Statement

Mental Model

Thinking in recursive sub-problems and hierarchical branching.

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. The Mental Model: The "Pearl Necklace"

Imagine the tree is a bunch of pearls (nodes) connected by strings. You can pick up the necklace by any single pearl and let the rest hang down.

• A path can go through a node and descend into both its children (forming an inverted 'V').
• However, to the node's parent, the path can only continue through one of those children (the one with the higher sum).

This duality is the key to solving the problem:

1. Locally: We check if LeftSum + RightSum + NodeValue is our global maximum.
2. Globally: We return NodeValue + max(LeftSum, RightSum) to our parent.

3. Visual Execution (Gain Propagation)

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

4. Java Implementation

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;

        // 1. Recursive call for subtrees
        // Optimization: If a subtree returns a negative gain, we treat it as 0
        // because adding a negative path will only decrease our total sum.
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);

        // 2. The "Aha!" Moment: Check the path that "peaks" at this node
        int currentPathSum = node.val + leftGain + rightGain;

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

        // 4. Return the maximum gain this node can offer to its parent
        // We can only pick ONE branch to pass upward.
        return node.val + Math.max(leftGain, rightGain);
    }
}

5. Verbal Interview Script (Staff Tier)

Interviewer: "Why do we return 0 if the maxGain is negative?"

You: "That is a critical pruning optimization. Since we are looking for the maximum path sum, any subtree that produces a total negative value is effectively 'useless' to any path passing through it. By taking Math.max(gain, 0), we are essentially deciding to not include that entire branch in our path. This handles trees with negative node values gracefully. Furthermore, this logic ensures that every node correctly evaluates whether it should be the 'Highest Point' of its own local path, or simply a 'Segment' of a path that continues up to its parent."

6. Performance Nuances (Staff Level)

1. Recursion Depth: Like all tree problems, the space complexity is $O(H)$ where $H$ is the tree height. For a skewed tree of 100,000 nodes, this will cause a StackOverflowError. A production-level Java implementation for massive trees would require an iterative approach using two stacks (simulating post-order traversal).
2. Global vs Local State: While I used a private field maxSum, in a thread-safe library, I would pass a single-element array int[] maxSum or a wrapper object through the recursive calls to ensure the function is pure and stateless at the class level.

7. Comparison: Path Sum I, II, vs III

6. Staff-Level Interview Follow-Ups

Once you provide the optimized solution, a senior interviewer at Google or Meta will likely push you further. Here is how to handle the most common follow-ups:

Follow-up 1: "How does this scale to a Distributed System?"

If the input data is too large to fit on a single machine (e.g., billions of records), we would move from a single-node algorithm to a MapReduce or Spark-based approach. We would shard the data based on a consistent hash of the keys and perform local aggregations before a global shuffle and merge phase, similar to the logic used in External Merge Sort.

Follow-up 2: "What are the Concurrency implications?"

In a multi-threaded Java environment, we must ensure that our state (e.g., the DP table or the frequency map) is thread-safe. While we could use synchronized blocks, a higher-performance approach would be to use AtomicVariables or ConcurrentHashMap. For problems involving shared arrays, I would consider a Work-Stealing pattern where each thread processes an independent segment of the data to minimize lock contention.

7. Performance Nuances (The Java Perspective)

1. Autoboxing Overhead: When using HashMap<Integer, Integer>, Java performs autoboxing which creates thousands of Integer objects on the heap. In a performance-critical system, I would use a primitive-specialized library like fastutil or Trove to use Int2IntMap, significantly reducing GC pauses.
2. Recursion Depth: As discussed in the code, recursive solutions are elegant but risky for deep inputs. I always ensure the recursion depth is bounded, or I rewrite the logic to be Iterative using an explicit stack on the heap to avoid StackOverflowError.

Key Takeaways

• A path can go through a node and descend into both its children (forming an inverted 'V').
• However, to the node's parent, the path can only continue through one of those children (the one with the higher sum).
• MANG Problem #10: Sudoku Solver (Constraint Search)

Read Next

• MANG Problem #10: Sudoku Solver (Constraint Search)
• Lesson: Binary Tree Depth and Balance Logic