How to Compute the Maximum Path Sum in a Binary Tree (C Solution)

Description

Given a non‑empty binary tree, return its maximum path sum. A path is any sequence of nodes from any node to any other node, must contain at least one node, and does not have to pass through the root.

Examples

Input: [1,2,3]
      1
     / \
    2   3
Output: 6

Input: [-10,9,20,null,null,15,7]
   -10
   /  \
  9   20
     /  \
    15   7
Output: 42

Analysis

The algorithm keeps a global variable (named max or result) to record the overall maximum path sum while a recursive helper returns the best sum that can be extended to the parent.

For a node a with left child b and right child c, three possible path configurations exist:

b + a + c

b + a + a_parent

a + c + a_parent

Case 1 represents a path that does not connect to the parent (or the node is the root). This case cannot be obtained by recursion but may still be the global maximum. Cases 2 and 3 are handled by recursion: the helper computes a+b and a+c, chooses the larger, and returns it to the parent. Negative contributions are discarded using max(0, x).

Brute‑Force Enumeration

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int result = -2147483648;
int helper(struct TreeNode* root){
    if (root == NULL) return 0;
    int left = helper(root->left);
    int right = helper(root->right);
    int threeNodeSum = root->val + left + right;
    int twoNodeSum = root->val + max(left, right);
    int oneNodeSum = root->val;
    int ret = max(twoNodeSum, oneNodeSum);
    int currentMax = max(ret, threeNodeSum);
    result = max(currentMax, result);
    return ret;
}
int max(int a, int b){
    return a > b ? a : b;
}
int maxPathSum(struct TreeNode* root){
    result = -2147483648;
    int temp = helper(root);
    return result;
}

Optimized Depth‑First Search

#define max(a, b) ((a) > (b) ? (a) : (b))
int maxPath = INT_MIN;
int dfs(struct TreeNode *root){
    if (root == NULL) {
        return 0;
    }
    // maximum sum from left subtree
    int left = dfs(root->left);
    // maximum sum from right subtree
    int right = dfs(root->right);
    // update global maximum with path that passes through the current node
    maxPath = max(left + right + root->val, maxPath);
    // return the maximum sum of a path that can be extended to the parent
    return max(0, max(left, right) + root->val);
}
int maxPathSum(struct TreeNode* root){
    // initialize with the smallest possible integer
    maxPath = INT_MIN;
    // depth‑first traversal
    dfs(root);
    return maxPath;
}