Binary Tree Maximum Path Sum – Meta (Facebook) Interview Question

Section 1: Introduction

In this lesson, we’re solving a well-known Meta (Facebook) interview question: Binary Tree Maximum Path Sum.

This is a classic problem often asked in technical interviews at top tech companies. It tests your understanding of recursion, tree traversal, and dynamic thinking.

Section 2: Problem Description

You are given the root of a binary tree. Your task is to return the maximum path sum among all possible paths in the tree.

Here’s how a valid path is defined:

• A path is any sequence of nodes where each adjacent pair is connected by a direct edge.

• A node can appear in the path only once.

• The path does not have to pass through the root.

• The total path sum is the sum of node values in the path.

Let’s look at an example:

Input:

root = [-10, 9, 20, null, null, 15, 7]

This represents the following binary tree:

      -10
      /  
     9   20
         / 
        15  7

The optimal path is:
15 → 20 → 7
So the maximum path sum is 15 + 20 + 7 = 42.

Section 3: High-Level Idea

To solve this problem efficiently, we use recursion with depth-first search (DFS).

The key idea is:

• At each node, we calculate the maximum gain we can obtain from its left and right subtrees.

• Then, we compute the path sum assuming the path passes through the current node and both children.

• We update a global variable to track the maximum path sum seen so far.

We also make sure to discard negative paths. If the left or right gain is negative, we treat it as zero — meaning, we don’t include it in the path.

Section 4: Code Walkthrough (C++)

Here’s the complete solution step by step:

class Solution {
public:
    int maxSum = INT_MIN;

    int maxGain(TreeNode* node) {
        if (!node) return 0;
        
        int leftGain = max(maxGain(node->left), 0);
        int rightGain = max(maxGain(node->right), 0);
        
        int currentPathSum = node->val + leftGain + rightGain;
        maxSum = max(maxSum, currentPathSum);
        
        return node->val + max(leftGain, rightGain);
    }

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

Explanation:

1. We declare a global variable maxSum, initialized to INT_MIN, to track the highest path sum found.

2. The recursive function maxGain():

   • Returns the maximum path sum starting from the current node and going downward.

   • If the node is null, we return 0.

   • For both left and right subtrees, we calculate the gain and ignore negative results using max(…, 0).

3. The total path through the current node is node->val + leftGain + rightGain. This is a candidate for the global maximum.

4. We update maxSum accordingly.

5. Finally, the function returns the maximum gain we can use to extend the path to the parent — either left or right.

This solution ensures that we consider all valid paths in the tree, including those that start and end at any node.

Section 5: Summary

Let’s summarize the key points:

• We use a post-order traversal to compute gains from bottom to top.

• We track the best full path that passes through each node using a global variable.

• We discard negative gains to avoid reducing the total sum.

• The final answer is stored in maxSum, which we return at the end.

This problem is a great example of combining tree traversal with dynamic thinking, and it’s a common interview question at Meta (Facebook) and other top-tier tech companies.