Maximum Path Sum in Binary Tree in DSA C

Mental Model

Find the highest sum you can get by traveling along any path in the tree, where a path can start and end at any node.

Analogy: Imagine a mountain range where each peak has a height (value). You want to find the highest total height you can get by walking along connected peaks, but you can start and stop anywhere.

      [10]
      /   \
   [2]    [10]
   / \      \
 [20] [1]   [-25]
             /  \
          [3]    [4]

Dry Run Walkthrough

Input: Binary tree: 10 -> 2, 10 -> 10, 2 -> 20, 2 -> 1, 10 -> -25, -25 -> 3, -25 -> 4

Goal: Find the maximum path sum anywhere in the tree

Step 1: Start at leaf node 20, max path sum is 20

20 (leaf) -> max path sum = 20

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

Step 2: At node 1, max path sum is 1

1 (leaf) -> max path sum = 1

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

Step 3: At node 2, calculate max path sum including children: max(20,1) + 2 = 22; max path through node 2 is 20 + 2 + 1 = 23

2 -> left=20, right=1, max single path=22, max path through node=23

Why: We consider max path including left or right child plus node, and max path passing through node

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

3 (leaf) -> max path sum = 3

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

Step 5: At leaf node 4, max path sum is 4

4 (leaf) -> max path sum = 4

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

Step 6: At node -25, max single path is max(3,4) + (-25) = max(3,4) - 25 = -21; max path through node is 3 + (-25) + 4 = -18

-25 -> left=3, right=4, max single path=-21, max path through node=-18

Why: Negative node reduces max path sum, so max single path can be negative

Step 7: At right child 10, max path sum is 10

10 -> max path sum = 10

Why: Max path sum down equals own value after ignoring negative child paths

Step 8: At root 10, max single path is max(22,10) + 10 = 32; max path through node is 22 + 10 + 10 = 42

10 -> left max single=22, right max single=10, max single path=32, max path through node=42

Why: Root combines max single paths from left and right plus its own value

Result:

Maximum path sum is 42
Final path example: 20 -> 2 -> 10 -> 10

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// Define tree node structure
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// Helper function to create a new node
TreeNode* newNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Global variable to keep track of max path sum
int maxSum;

// Recursive function to find max path sum starting from current node
int maxPathDown(TreeNode* node) {
    if (node == NULL) return 0;

    // Recursively get max path sum from left child
    int left = maxPathDown(node->left);
    // Recursively get max path sum from right child
    int right = maxPathDown(node->right);

    // Ignore negative paths by taking max with 0
    if (left < 0) left = 0;
    if (right < 0) right = 0;

    // Calculate max path sum passing through this node
    int currentSum = node->val + left + right;

    // Update global maxSum if currentSum is greater
    if (currentSum > maxSum) maxSum = currentSum;

    // Return max path sum going down from this node
    int returnVal = node->val + (left > right ? left : right);
    return returnVal;
}

// Function to find max path sum in the tree
int maxPathSum(TreeNode* root) {
    maxSum = INT_MIN;
    maxPathDown(root);
    return maxSum;
}

int main() {
    // Build the example tree
    TreeNode* root = newNode(10);
    root->left = newNode(2);
    root->right = newNode(10);
    root->left->left = newNode(20);
    root->left->right = newNode(1);
    root->right->right = newNode(-25);
    root->right->right->left = newNode(3);
    root->right->right->right = newNode(4);

    int result = maxPathSum(root);
    printf("Maximum Path Sum: %d\n", result);
    return 0;
}

if (node == NULL) return 0;

stop recursion at leaf's child

int left = maxPathDown(node->left);

recurse left subtree to get max path sum down

int right = maxPathDown(node->right);

recurse right subtree to get max path sum down

if (left < 0) left = 0; if (right < 0) right = 0;

ignore negative paths to avoid reducing sum

int currentSum = node->val + left + right;

calculate max path sum passing through current node

if (currentSum > maxSum) maxSum = currentSum;

update global max if current path is better

return node->val + (left > right ? left : right);

return max path sum going down one side for parent's use

Output

Maximum Path Sum: 42

Complexity Analysis

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

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

vs Alternative: Naive approach checking all paths is O(n^2) or worse; this uses bottom-up recursion for O(n)

Edge Cases

Empty tree

Returns INT_MIN or no path sum

DSA C

if (node == NULL) return 0;

All negative values

Returns the least negative single node value as max path sum

DSA C

maxSum initialized to INT_MIN and negative paths ignored by max(0, left/right)

Single node tree

Returns the value of the single node

DSA C

base case handles leaf nodes returning their value

When to Use This Pattern

When asked to find the maximum sum path in a tree that can start and end anywhere, use a recursive bottom-up approach that tracks max sums including and passing through each node.

Common Mistakes

Mistake: Not ignoring negative child paths, which lowers the max sum
Fix: Use max(0, left) and max(0, right) to ignore negative sums

Mistake: Returning max path sum including both children to parent, which breaks path definition
Fix: Return max path sum going down only one side to parent

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.

The key is to track max sums passing through nodes and ignore negative paths.

Practice

1. What does the "maximum path sum" in a binary tree represent?

easy

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

B. The sum of all node values in the tree

C. The largest sum of values along any path between two nodes

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

Solution

1. Step 1: Understand the path definition

   The path can start and end at any two nodes, not necessarily root or leaf.

2. Step 2: Identify maximum sum meaning

   It is the largest 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 -> Option C

4. Quick Check:

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

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

Common Mistakes:

• Thinking it must start at root
• Confusing with sum of all nodes
• Considering only leaf nodes

2. Which of the following C function signatures is correct for a recursive function to find maximum path sum in a binary tree node defined as struct TreeNode?

easy

A. int maxPathSum(struct TreeNode* root);

B. void maxPathSum(struct TreeNode root);

C. int maxPathSum(struct TreeNode root);

D. int maxPathSum(struct TreeNode** root);

Solution

1. Step 1: Understand parameter passing for trees in C

   Binary trees are usually passed as pointers to nodes, so struct TreeNode* is correct.

2. Step 2: Check return type and parameter correctness

   Function returns int (maximum sum), and parameter is pointer to root node, so int maxPathSum(struct TreeNode* root); is correct.

3. Final Answer:

   int maxPathSum(struct TreeNode* root); -> Option A

4. Quick Check:

   Use pointer parameter and int return type [OK]

Hint: Use pointer to struct for tree nodes in C functions [OK]

Common Mistakes:

• Passing struct by value instead of pointer
• Using void return type instead of int
• Using double pointer unnecessarily

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

    1
   / \
  2   3

medium

A. 5

B. 6

C. 4

D. 3

Solution

1. Step 1: Identify all possible paths and their sums

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

2. Step 2: Find the maximum sum among these paths

   Maximum sum is 6 from path 2->1->3.

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Sum of 2 + 1 + 3 = 6 [OK]

Hint: Check paths through root connecting left and right [OK]

Common Mistakes:

• Considering only root to leaf paths
• Ignoring paths that go through root connecting children
• Choosing max node value instead of path sum

4. Consider this buggy C code snippet for maximum path sum calculation:

int maxPathSumUtil(struct TreeNode* root, int* maxSum) {
    if (!root) return 0;
    int left = maxPathSumUtil(root->left, maxSum);
    int right = maxPathSumUtil(root->right, maxSum);
    int maxSingle = max(max(left, right) + root->val, root->val);
    int maxTop = max(maxSingle, left + right + root->val);
    *maxSum = max(*maxSum, maxTop);
    return maxSingle;
}

What is the main bug in this code?

medium

A. It does not update maxSum pointer correctly

B. It does not handle negative node values correctly

C. It returns maxTop instead of maxSingle

D. It uses max function without defining it

Solution

1. Step 1: Check usage of max function

   The code uses max() but C standard library does not have max function by default; it must be defined or replaced.

2. Step 2: Verify other logic parts

   Return and pointer update logic is correct; negative values handled by max comparisons.

3. Final Answer:

   It uses max function without defining it -> Option D

4. Quick Check:

   max() must be defined or replaced in C [OK]

Hint: Remember C has no built-in max function [OK]

Common Mistakes:

• Assuming max() is built-in in C
• Confusing return values with maxSum update
• Ignoring pointer usage correctness

5. You want to find the maximum path sum in a binary tree where some nodes have negative values. Which approach correctly handles negative values to find the maximum path sum?

hard

A. Use recursion to compute max path sums including negative values and update global max accordingly

B. Calculate sum of all nodes and subtract minimum negative node value

C. Only consider paths that include positive nodes and skip negative nodes completely

D. Ignore negative values by treating them as zero during recursion

Solution

1. Step 1: Understand handling of negative values in max path sum

   Negative values can reduce path sums, so recursion must consider them but choose max sums carefully.

2. Step 2: Use recursion with max comparisons to update global max

   Recursion returns max single path sum including negative values, updating global max with max of left+right+node or single path sums.

3. Final Answer:

   Use recursion to compute max path sums including negative values and update global max accordingly -> Option A

4. Quick Check:

   Include negatives but choose max sums carefully [OK]

Hint: Include negatives but pick max sums in recursion [OK]

Common Mistakes:

• Ignoring negative nodes completely
• Treating negatives as zero forcibly
• Using simple sums without max comparisons