Maximum Path Sum in Binary Tree in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to define the structure for a binary tree node.

DSA C

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *[1];
} TreeNode;

Drag options to blanks, or click blank then click option'

Aright

Bparent

Cnext

Dchild

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'parent' or 'next' instead of 'right' for the right child pointer.

The right child pointer in a binary tree node is named 'right'.

2fill in blank

medium

Complete the code to update the maximum path sum if the current path sum is greater.

DSA C

if (currentSum > [1]) {
    maxSum = currentSum;
}

Drag options to blanks, or click blank then click option'

AcurrentSum - 1

BmaxSum

CmaxSum + 1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing currentSum with maxSum + 1 or other incorrect values.

We compare currentSum with maxSum to update maxSum if currentSum is greater.

3fill in blank

hard

Fix the error in the recursive function to return the maximum gain from the current node.

DSA C

int maxGain(TreeNode* node, int* maxSum) {
    if (node == NULL) return 0;
    int leftGain = max(0, maxGain(node->left, maxSum));
    int rightGain = max(0, maxGain(node->[1], maxSum));
    int priceNewpath = node->val + leftGain + rightGain;
    if (priceNewpath > *maxSum) *maxSum = priceNewpath;
    return node->val + (leftGain > rightGain ? leftGain : rightGain);
}

Drag options to blanks, or click blank then click option'

Anext

Bparent

Cright

Dchild

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'parent' or 'next' instead of 'right' for the right child pointer.

The right child pointer is 'right', so we recurse on node->right.

4fill in blank

hard

Fill both blanks to complete the max function and the recursive call for left child.

DSA C

int max(int a, int b) {
    return (a [1] b) ? a : b;
}

int maxGain(TreeNode* node, int* maxSum) {
    if (node == NULL) return 0;
    int leftGain = max(0, maxGain(node->[2], maxSum));

Drag options to blanks, or click blank then click option'

A>

B<

Cleft

Dright

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' in max function or wrong child pointer names.

The max function uses '>' to return the larger value, and the left child pointer is 'left'.

5fill in blank

hard

Fill all three blanks to complete the main function that initializes maxSum and calls maxGain.

DSA C

int maxPathSum(TreeNode* root) {
    int maxSum = [1];
    maxGain(root, &[2]);
    return [3];
}

Drag options to blanks, or click blank then click option'

A0

BmaxSum

D-2147483648

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing maxSum to 0 or not passing it by reference.

maxSum is initialized to the smallest integer, passed by reference, and returned after computation.

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