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.

Practice

1. What does the term Maximum Path Sum in a binary tree mean?

easy

A. The sum of all node values in the tree

B. The largest sum of values along any path between two nodes in the tree

C. The maximum value of a single node in the tree

D. The sum of values from root to the deepest leaf only

Solution

1. Step 1: Understand the path definition

   A path in a binary tree can start and end at any nodes, not necessarily root or leaf.

2. Step 2: Define maximum path sum

   It is the highest sum of node values along any such path in the tree.

3. Final Answer:

   The largest sum of values along any path between two nodes in the tree -> Option B

4. Quick Check:

   Maximum path sum means highest sum on any path [OK]

Hint: Maximum path sum is any path, not just root to leaf [OK]

Common Mistakes:

• Confusing maximum path sum with sum of all nodes
• Thinking path must start at root
• Considering only leaf nodes for path ends

2. Which of the following C++ function signatures is correct for a helper function that returns the maximum path sum starting from a given node in a binary tree?

easy

A. int maxPathSumHelper(TreeNode* root, int& maxSum);

B. void maxPathSumHelper(TreeNode root, int maxSum);

C. int maxPathSumHelper(TreeNode root);

D. int maxPathSumHelper(TreeNode* root);

Solution

1. Step 1: Understand parameter passing

   The function needs to update maxSum globally, so it must be passed by reference.

2. Step 2: Check pointer usage

   TreeNode* is used to pass node pointers, not objects directly.

3. Final Answer:

   int maxPathSumHelper(TreeNode* root, int& maxSum); -> Option A

4. Quick Check:

   Use pointer and reference for maxSum [OK]

Hint: Pass maxSum by reference and node as pointer [OK]

Common Mistakes:

• Passing TreeNode by value instead of pointer
• Not passing maxSum by reference
• Using void return type instead of int

3. Consider the following binary tree:

    1
   / \
  2   3

What is the maximum path sum returned by the standard algorithm?

medium

A. 3

B. 5

C. 4

D. 6

Solution

1. Step 1: Calculate path sums including root

   Paths: 2->1->3 sum = 6, 2->1 sum = 3, 1->3 sum = 4.

2. Step 2: Identify maximum sum

   The maximum path sum is 6 from path 2->1->3.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   2+1+3 = 6 [OK]

Hint: Check all paths including both children and root [OK]

Common Mistakes:

• Considering only root-to-leaf paths
• Ignoring paths passing through root
• Adding only one child value

4. Given this buggy code snippet for maximum path sum, what is the main error?

int maxPathSumHelper(TreeNode* root, int& maxSum) {
  if (!root) return 0;
  int left = maxPathSumHelper(root->left, maxSum);
  int right = maxPathSumHelper(root->right, maxSum);
  int current = root->val + left + right;
  maxSum = max(maxSum, current);
  return root->val + max(left, right);
}

What is the bug?

medium

A. It does not ignore negative path sums

B. It returns sum of both children instead of max child

C. It updates maxSum incorrectly

D. It does not handle null root

Solution

1. Step 1: Analyze negative path sums handling

   The code adds left and right directly without ignoring negative sums, which can reduce maxSum.

2. Step 2: Correct approach for negatives

   Should use max(0, left) and max(0, right) to ignore negative sums.

3. Final Answer:

   It does not ignore negative path sums -> Option A

4. Quick Check:

   Negative sums must be ignored to maximize path sum [OK]

Hint: Use max(0, child) to ignore negative sums [OK]

Common Mistakes:

• Adding negative child sums reduces maxSum
• Returning sum of both children instead of max child
• Not checking for null root

5. Given the binary tree below, what is the maximum path sum?

       -10
       /  \
      9   20
          / \
         15  7

Choose the correct maximum path sum.

hard

A. 27

B. 35

C. 42

D. 15

Solution

1. Step 1: Calculate max path sums for subtrees

   Left subtree max path sum is 9. Right subtree max path sum includes 20 + 15 + 7 = 42.

2. Step 2: Consider paths through root

   Path through root: -10 + max(0,9) + max(0,15+20+7) = -10 + 9 + 42 = 41, less than 42.

3. Step 3: Identify maximum path sum

   The maximum path sum is 42 from path 15->20->7.

4. Final Answer:

   42 -> Option C

5. Quick Check:

   15+20+7 = 42 [OK]

Hint: Check all subtree sums and paths through root [OK]

Common Mistakes:

• Including negative root value in max path sum
• Ignoring paths not passing through root
• Adding left and right children without max(0, val)