Maximum Path Sum in Binary Tree in DSA C - Build from Scratch

Maximum Path Sum in Binary Tree

📖 Scenario: Imagine you are working with a tree-like structure that represents a network of roads connecting cities. Each road has a value representing its importance. You want to find the path through this network that has the highest total importance value. This path can start and end at any city, but it must follow the roads connecting them.

🎯 Goal: Build a program in C that creates a binary tree with specific node values, then calculates the maximum path sum in the tree. The maximum path sum is the highest sum of node values along any path in the tree, where the path can start and end at any node.

📋 What You'll Learn

Create a binary tree with the exact node values and structure given.

Use a helper variable to keep track of the maximum path sum found so far.

Implement a recursive function to calculate the maximum path sum including paths through each node.

Print the final maximum path sum after processing the entire tree.

💡 Why This Matters

🌍 Real World

Finding maximum path sums in trees is useful in network analysis, such as finding the most valuable route in a road or communication network.

💼 Career

Understanding tree traversal and recursion is essential for software engineering roles involving data structures, algorithms, and problem solving.

1

Create the Binary Tree Structure

Define a struct Node with int data, and pointers left and right. Then create nodes to build this exact binary tree:

1
/ \ 2 3
/ \ \ 4 -5 6

Use malloc to allocate nodes and assign the exact data values shown.

DSA C

# Define struct Node and create the binary tree nodes
# Your code here

Hint

Start by defining the Node structure. Then write a helper function newNode to create nodes easily. Finally, build the tree by linking nodes as shown.

2

Add a Global Variable to Track Maximum Path Sum

Declare a global variable called maxSum and initialize it to INT_MIN from limits.h. This variable will store the highest path sum found during traversal.

DSA C

#include 

int maxSum = INT_MIN;  // Your code here

Hint

Include limits.h to use INT_MIN. Declare maxSum outside main so it is global.

3

Implement Recursive Function to Find Maximum Path Sum

Write a recursive function called maxPathSumUtil that takes a struct Node* parameter called node. It should return the maximum path sum for paths starting at node and update the global maxSum if a higher path sum is found. Use these steps:
- If node is NULL, return 0.
- Recursively get maximum path sums from left and right children, but ignore negative sums by taking max with 0.
- Calculate current path sum as node->data + left + right.
- Update maxSum if current path sum is greater.
- Return node->data + max(left, right).

DSA C

int maxPathSumUtil(struct Node* node) {
    // Your code here
}

Hint

Use recursion to explore left and right children. Ignore negative sums by replacing them with zero. Update maxSum if the current path sum is bigger. Return the max path sum including the current node and one child.

4

Print the Maximum Path Sum

In main, after calling maxPathSumUtil(root), print the value of the global variable maxSum using printf.

DSA C

    maxPathSumUtil(root);
    // Print the maximum path sum below
    // Your code here

Hint

Use printf("%d\n", maxSum); to print the maximum path sum after the recursive call.

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