Neetcode - Binary Tree Maximum Path Sum

Think in steps, not leaps.

This question is not much different from the previous tree problems we have solved. What we need to pay attention to is how to compare and obtain the maximum path sum and when to dive deeper into the tree. We are not limited to paths starting at the root; a path can start and end at any node that connects to other nodes. However, only subtrees that maintain the binary tree structure are considered as candidates.

Therefore, in a tree that extends all the way down to the left, forming essentially a linked list, it is still considered a valid candidate because it follows the binary tree structure. Here's the code:

class Solution {
private:
    int dfs(TreeNode *node, int &max_sum) {
        if (node == nullptr) return 0;
        
        int left = max(dfs(node->left, max_sum), 0);
        int right = max(dfs(node->right, max_sum), 0);

        int current_sum = node->val + left + right;
        max_sum = max(max_sum, current_sum);
        return node->val + max(left, right);
    }
public: 
    int maxPathSum(TreeNode* root) {
        int m = -10000;
        dfs(root, m);
        return m;
    }
};

We see that the code starts by passing in the root node and uses a reference to track the maximum path sum during recursive calls.

• Base case: When the node is null, we simply return 0 as the termination condition.
• Recursive step: If the node is not null, we recursively explore the left and right subtrees.
• Current node sum: At each node, we compute the path sum through the current node as the sum of the node’s value plus the contributions from the left and right subtrees.
• Return value: We return the current node value plus the maximum of the left and right subtree sums. This is because, for the upward path toward the parent, we only consider the single branch that contributes the maximum sum.

This approach ensures that all possible paths are considered while correctly propagating the maximum single-branch sums upward and updating the global maximum when a path passes through a node. That's it.