Maximum Path Sum in Binary Tree in DSA C++

Mental Model

Find the highest sum of values along any path in a tree, where a path can start and end at any node.

Analogy: Imagine a mountain range where each peak has a height. You want to find the highest possible trail that can go up and down connecting any peaks, not necessarily starting at the base or ending at the top.

      1
     / \
    2   3
   / \
  4   5

Each number is a node value. Paths can go up and down but cannot revisit nodes.

Dry Run Walkthrough

Input: Binary tree: 1 -> 2 -> 4, 2 -> 5, 1 -> 3

Goal: Find the maximum sum path in the tree, which can start and end anywhere.

Step 1: Start at node 4, max path sum from 4 is 4

Node 4: max path sum = 4

Why: Leaf nodes have max path sum equal to their own value

Step 2: At node 5, max path sum from 5 is 5

Node 5: max path sum = 5

Why: Leaf nodes have max path sum equal to their own value

Step 3: At node 2, calculate max path sum including left and right children: max(4,5) + 2 = 7, also consider path through node 2: 4 + 2 + 5 = 11

Node 2: max path sum from node = 7, max path sum overall = 11

Why: We consider max path sum from one child plus node, and also path through node connecting both children

Step 4: At node 3, max path sum from 3 is 3

Node 3: max path sum = 3

Why: Leaf node max path sum is node value

Step 5: At node 1, calculate max path sum from children: max(7,3) + 1 = 8, also consider path through node 1: 7 + 1 + 3 = 11

Node 1: max path sum from node = 8, max path sum overall = 11

Why: Check max path sum including node and one child, and path through node connecting both children

Result:

Maximum path sum in tree = 11

Annotated Code

DSA C++

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

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

class Solution {
public:
    int maxSum = INT_MIN;

    int maxGain(TreeNode* node) {
        if (!node) return 0;
        // max sum on the left subtree; ignore negative sums
        int leftGain = max(maxGain(node->left), 0);
        // max sum on the right subtree; ignore negative sums
        int rightGain = max(maxGain(node->right), 0);

        // price to start a new path where `node` is the highest node
        int priceNewPath = node->val + leftGain + rightGain;

        // update maxSum if priceNewPath is better
        maxSum = max(maxSum, priceNewPath);

        // for recursion: return max gain if continue the same path
        return node->val + max(leftGain, rightGain);
    }

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

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    Solution sol;
    cout << sol.maxPathSum(root) << "\n";
    return 0;
}

if (!node) return 0;

stop recursion at null nodes

int leftGain = max(maxGain(node->left), 0);

calculate max gain from left child ignoring negative sums

int rightGain = max(maxGain(node->right), 0);

calculate max gain from right child ignoring negative sums

int priceNewPath = node->val + leftGain + rightGain;

calculate max path sum with current node as root connecting both children

maxSum = max(maxSum, priceNewPath);

update global max path sum if current path is better

return node->val + max(leftGain, rightGain);

return max gain to parent continuing one path

Output

11

Complexity Analysis

Time: O(n) because we visit each node once in the tree

Space: O(h) where h is the height of the tree due to recursion stack

vs Alternative: Naive approach might try all paths explicitly with O(n^2) or worse; this uses recursion and pruning negative sums for efficiency

Edge Cases

Tree with all negative values

The algorithm returns the single largest node value as max path sum

DSA C++

int leftGain = max(maxGain(node->left), 0);

Tree with single node

Returns the value of the single node as max path sum

DSA C++

if (!node) return 0;

Tree with zero values

Zero values are included if they improve the path sum, otherwise ignored

DSA C++

int leftGain = max(maxGain(node->left), 0);

When to Use This Pattern

When asked to find the maximum sum path in a tree that can start and end anywhere, use the max path sum pattern with recursion and tracking max gains from children.

Common Mistakes

Mistake: Not ignoring negative child sums, which lowers the max path sum
Fix: Use max(childGain, 0) to ignore negative sums

Mistake: Returning sum of both children plus node to parent, causing incorrect path sums
Fix: Return node value plus max of one child's gain to parent to keep path linear

Summary

Finds the highest sum of values along any path in a binary tree.

Use when you need the max sum path that can start and end at any node in the tree.

The key is to track max gains from children ignoring negative sums and update global max with paths through each node.