Maximum Path Sum in Binary Tree in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Maximum Path Sum Calculation

What is the maximum path sum of the following binary tree?

DSA C

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// Tree structure:
//       1
//      / \
//     2   3

int maxPathSumHelper(struct TreeNode* root, int* maxSum) {
    if (!root) return 0;
    int left = maxPathSumHelper(root->left, maxSum);
    int right = maxPathSumHelper(root->right, maxSum);
    int max_single = (left > right ? left : right) + root->val;
    if (max_single < root->val) max_single = root->val;
    int max_top = left + right + root->val;
    if (*maxSum < max_top) *maxSum = max_top;
    if (*maxSum < max_single) *maxSum = max_single;
    return max_single;
}

int maxPathSum(struct TreeNode* root) {
    int maxSum = root->val;
    maxPathSumHelper(root, &maxSum);
    return maxSum;
}

// Construct tree nodes
struct TreeNode n1 = {1, NULL, NULL};
struct TreeNode n2 = {2, NULL, NULL};
struct TreeNode n3 = {3, NULL, NULL};

// Link nodes
n1.left = &n2;
n1.right = &n3;

int result = maxPathSum(&n1);
printf("%d\n", result);

A 6

B 5

C 3

D 4

💡 Hint

Consider paths that can go through the root and both children.

The maximum path sum is 2 + 1 + 3 = 6. The path includes left child, root, and right child.

🧠 Conceptual

intermediate

Understanding Path Sum Constraints

Which statement about the maximum path sum in a binary tree is TRUE?

A The path must always start at the root node.

B The path must include all nodes in the tree.

C The path can start and end at any nodes in the tree.

D The path can only go from root to leaf nodes.

💡 Hint

Think about whether the path is restricted to root or leaves.

The maximum path sum can be any path connecting nodes in the tree, not necessarily starting at root or ending at leaves.

🔧 Debug

advanced

Identify the Bug in Maximum Path Sum Code

What error will this code produce when calculating maximum path sum?

DSA C

int maxPathSumHelper(struct TreeNode* root, int* maxSum) {
    if (!root) return 0;
    int left = maxPathSumHelper(root->left, maxSum);
    int right = maxPathSumHelper(root->right, maxSum);
    int max_single = (left > right ? left : right) + root->val;
    int max_top = left + right + root->val;
    if (*maxSum < max_top) *maxSum = max_top;
    if (*maxSum < max_single) *maxSum = max_single;
    return max_single;
}

int maxPathSum(struct TreeNode* root) {
    int maxSum = 0;
    maxPathSumHelper(root, &maxSum);
    return maxSum;
}

A Returns zero always regardless of tree values

B Causes segmentation fault due to null pointer

C Compiles but returns max sum correctly

D Returns incorrect max sum if all values are negative

💡 Hint

Check initial maxSum value and how negative values are handled.

Initializing maxSum to 0 causes incorrect results if all node values are negative because maxSum never updates to negative values.

📝 Syntax

advanced

Identify Syntax Error in Recursive Function

Which option contains a syntax error in the maxPathSumHelper function?

DSA C

int maxPathSumHelper(struct TreeNode* root, int* maxSum) {
    if (!root) return 0
    int left = maxPathSumHelper(root->left, maxSum);
    int right = maxPathSumHelper(root->right, maxSum);
    int max_single = (left > right ? left : right) + root->val;
    int max_top = left + right + root->val;
    if (*maxSum < max_top) *maxSum = max_top;
    if (*maxSum < max_single) *maxSum = max_single;
    return max_single;
}

A Missing semicolon after 'return 0' statement

B Incorrect pointer dereference of maxSum

C Wrong function return type

D Missing braces for if statement

💡 Hint

Look carefully at the line with 'return 0'.

The line 'if (!root) return 0' is missing a semicolon at the end, causing a syntax error.

🚀 Application

expert

Maximum Path Sum with Negative Values

Given the binary tree below, what is the maximum path sum? // Tree structure: // -10 // / \ // 9 20 // / \ // 15 7

DSA C

struct TreeNode n1 = {-10, NULL, NULL};
struct TreeNode n2 = {9, NULL, NULL};
struct TreeNode n3 = {20, NULL, NULL};
struct TreeNode n4 = {15, NULL, NULL};
struct TreeNode n5 = {7, NULL, NULL};

n1.left = &n2;
n1.right = &n3;
n3.left = &n4;
n3.right = &n5;

int result = maxPathSum(&n1);
printf("%d\n", result);

A 35

B 42

C 27

D 20

💡 Hint

Consider the path 15 -> 20 -> 7 and also paths including root.

The maximum path sum is 15 + 20 + 7 = 42. The path does not include the root -10 because it reduces the sum.

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