Frequently Asked at Google — This problem has been reported multiple times in recent Google L4 interviews.

Binary Tree Maximum Path Sum (LC 124)

Problem Statement

A path in a binary tree is a sequence of nodes where each adjacent pair is connected by an edge. A path must contain at least one node and does not need to pass through the root. Given the root of a binary tree, return the maximum sum of any such path.

Example 1:

Input:  root = [1,2,3]
Output: 6
Explanation: 2 -> 1 -> 3 sums to 6.

Example 2:

Input:  root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: 15 -> 20 -> 7 sums to 42.

Constraints:

• 1 <= number of nodes <= 3 * 10^4
• -1000 <= Node.val <= 1000

Difficulty: Hard

---

Pattern Recognition

• Input structure: binary tree, node values can be negative.
• What are we optimizing? maximum sum over all paths, where a path can bend at any node.
• Pattern: postorder DFS returning a "gain" value plus a global maximum.
• Why: at every node, a path either ends there (contributes value + maxLeftGain + maxRightGain) or continues upward (contributes value + max(leftGain, rightGain)). The two cases require different return semantics; the global max captures the "ends here" case, the return value feeds the parent.

This dual-return trick — gain(node) returns one thing while updating a global — is the single most commonly asked Google tree idiom.

---

Approach

Brute Force

For every node, treat it as the bend point and do BFS/DFS from both children, find the best downward path each way, sum. O(n^2) time. TLE on deep trees.

Optimal — DFS With Two Return Semantics

Key Insight: gain(node) returns the max sum of a path that starts at node and goes downward. Inside the function, you also compute the "bend at node" candidate node.val + leftGain + rightGain and update a global answer.

best = -infinity

def gain(node):
    if node is null: return 0
    leftGain = max(gain(node.left), 0)    // drop negative branches
    rightGain = max(gain(node.right), 0)
    best = max(best, node.val + leftGain + rightGain)  // bend candidate
    return node.val + max(leftGain, rightGain)         // continue upward

gain(root)
return best

• Negative children contribute zero because not taking that branch is always an option.
• The bend candidate uses both children; the upward return can only use one.

Time: O(n) — each node visited once. Space: O(h) recursion stack, where h is tree height (O(n) worst case, O(log n) balanced).

---

Walkthrough

Tree: [-10, 9, 20, null, null, 15, 7] →

        -10
       /    \
      9      20
            /  \
           15   7

Postorder traversal:

Node	leftGain	rightGain	bend candidate	return
9	0	0	9+0+0=9	9
15	0	0	15	15
7	0	0	7	7
20	max(15,0)=15	max(7,0)=7	20+15+7=42 ← new best	20+max(15,7)=35
-10	max(9,0)=9	max(35,0)=35	-10+9+35=34	-10+max(9,35)=25

best = 42. Return 42.

Notice at root -10 the bend candidate (34) loses to the 20-node's candidate (42). Also notice we never propagate negative branches upward.

---

Implementation

TypeScript

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
        this.val = val; this.left = left; this.right = right;
    }
}

function maxPathSum(root: TreeNode | null): number {
    let best = -Infinity;

    const gain = (node: TreeNode | null): number => {
        if (!node) return 0;
        const leftGain = Math.max(gain(node.left), 0);
        const rightGain = Math.max(gain(node.right), 0);
        best = Math.max(best, node.val + leftGain + rightGain); // path bends at node
        return node.val + Math.max(leftGain, rightGain);        // path continues upward
    };

    gain(root);
    return best;
}

C++

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
    int best = INT_MIN;
    int gain(TreeNode* node) {
        if (!node) return 0;
        int leftGain = max(gain(node->left), 0);
        int rightGain = max(gain(node->right), 0);
        best = max(best, node->val + leftGain + rightGain);
        return node->val + max(leftGain, rightGain);
    }
public:
    int maxPathSum(TreeNode* root) {
        gain(root);
        return best;
    }
};

Watch out:

1. Initializing best to 0 fails on all-negative trees — the minimum possible path is the single largest (least negative) node. Use -Infinity / INT_MIN.
2. Returning node.val + leftGain + rightGain (the bend candidate) to the parent is wrong — that "path" enters and leaves node, so it cannot extend upward.
3. Forgetting to clamp children at 0 causes negative paths to drag the bend candidate down.

---

Complexity Analysis

	Time	Space
Brute Force	O(n^2)	O(h)
Optimal DFS	O(n)	O(h)

Bottleneck: every node contributes once to the answer; O(n) is optimal. Space is the recursion stack; iterative postorder can swap stack for an explicit stack but does not beat O(h).

---

Edge Cases

1. Single node — answer is node.val (possibly negative). The leaf case of gain covers it.
2. All negative values — answer is the largest single node. Initialization to -Infinity plus clamping children at 0 handles it.
3. Linear tree (skewed) — stack depth O(n); mention you might use iterative postorder in production for very deep trees.
4. Perfect balanced tree — stack depth O(log n).
5. Mixed zero values — zeros never hurt; the clamp treats them as neutral.
6. Null root — return 0 or handle per spec; LeetCode guarantees at least one node.

---

Related Problems

• LC 543 — Diameter of Binary Tree — Same DFS pattern, counts edges instead of sums values.
• LC 687 — Longest Univalue Path — Same DFS pattern with an extra value-equality check.
• LC 1372 — Longest ZigZag Path in a Binary Tree — Return two quantities (left-going, right-going) from each node.
• LC 968 — Binary Tree Cameras — Postorder DFS returning a state, not a number.

---

What Is Expected at Each Level

Junior: Recognize tree DFS. Probably needs a hint to split "path through node" from "path starting at node". Arrives at working code with guidance.

Mid-level: Writes the two-return idiom fluently, handles negative values correctly, states O(n) time and O(h) space.

Senior (L4 target): Verbalizes the invariant ("return what extends upward, update global with the bend"), proves why clamping at zero is safe, and naturally extends the same trick to LC 543, LC 687, LC 1372 when the interviewer pivots. Discusses when to switch to iterative postorder for production robustness.