DP on Trees Maximum Path Sum in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Maximum Path Sum in a Simple Binary Tree

What is the output of the following code that calculates the maximum path sum in a binary tree?

DSA C

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

int max(int a, int b) { return (a > b) ? a : b; }

int maxPathSumUtil(struct Node* root, int* res) {
    if (!root) return 0;
    int left = maxPathSumUtil(root->left, res);
    int right = maxPathSumUtil(root->right, res);
    int max_single = max(max(left, right) + root->val, root->val);
    int max_top = max(max_single, left + right + root->val);
    if (*res < max_top) *res = max_top;
    return max_single;
}

int maxPathSum(struct Node* root) {
    int res = -1000000;
    maxPathSumUtil(root, &res);
    return res;
}

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

// Expected call: maxPathSum(root);

A 6

B 5

C 3

D 1

💡 Hint

Consider the path that includes both left and right children plus the root.

The maximum path sum is from node 2 to node 1 to node 3, which sums to 2 + 1 + 3 = 6.

❓ Predict Output

intermediate

Maximum Path Sum with Negative Values

What is the output of the maximum path sum function for the following tree with negative values?

DSA C

// Tree structure:
//       -10
//       /  \
//      9   20
//          / \
//         15  7

// Using the same maxPathSum function as before.

A 42

B 35

C 27

D -10

💡 Hint

The maximum path may not include the root if it reduces the sum.

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

🧠 Conceptual

advanced

Understanding the Role of max_single and max_top in DP on Trees

In the DP solution for maximum path sum on trees, what does the variable max_single represent?

A The maximum path sum excluding the current node

B The maximum path sum including the current node and at most one child path

C The maximum path sum including the current node and both children paths

D The sum of values of all nodes in the tree

💡 Hint

Think about the path that can be extended upwards to the parent.

max_single is the maximum sum of a path starting at the current node and extending down to one child or no child, used to connect to the parent node.

❓ Predict Output

advanced

Output of Maximum Path Sum in a Tree with Single Node

What is the output of the maximum path sum function when the tree has only one node with value -5?

DSA C

// Tree structure:
//    -5

// Using the same maxPathSum function as before.

A INT_MIN

B 0

C 5

D -5

💡 Hint

The maximum path sum in a single node tree is the node's value itself.

With only one node, the maximum path sum is the value of that node, even if negative.

🧠 Conceptual

expert

Why is it necessary to track a global maximum in DP on Trees Maximum Path Sum?

Why does the DP solution for maximum path sum on trees use a global variable to track the maximum path sum instead of returning it directly from the recursive function?

A Because the global variable stores the sum of all leaf nodes only

B Because the recursive function cannot return integers in C

C Because the maximum path can be anywhere in the tree and may not pass through the root of the current subtree

D Because the maximum path sum is always the sum of all nodes in the tree

💡 Hint

Consider paths that do not include the parent node.

The maximum path sum can be a path that passes through any node, not necessarily the root of the current subtree, so a global variable tracks the best found so far.

Practice

1. What does the "Maximum Path Sum" in a tree represent in the context of dynamic programming on trees?

easy

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

B. The number of nodes in the longest path of the tree

C. The sum of all node values in the tree

D. The height of the tree

Solution

1. Step 1: Understand the problem definition

   The maximum path sum is about finding the path between any two nodes that yields the highest sum of node values.

2. Step 2: Differentiate from other tree properties

   Unlike longest path or height, maximum path sum focuses on the sum of node values, not count or depth.

3. Final Answer:

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

4. Quick Check:

   Maximum path sum = largest node value sum [OK]

Hint: Maximum path sum is about sums, not counts or heights [OK]

Common Mistakes:

• Confusing maximum path sum with longest path length
• Thinking it is the sum of all nodes
• Mixing it up with tree height

2. Which of the following is the correct base case initialization for a recursive function computing maximum path sum in a binary tree node in C?

easy

A. if (node == NULL) return INT_MIN;

B. if (node == NULL) return -1;

C. if (node == NULL) return 1;

D. if (node == NULL) return 0;

Solution

1. Step 1: Understand base case for null nodes

   For maximum path sum, null nodes should contribute 0 to the path sum as they do not add any value.

2. Step 2: Choose appropriate return value

   Returning 0 ensures that null nodes do not affect the sum and allows the recursion to proceed correctly.

3. Final Answer:

   if (node == NULL) return 0; -> Option D

4. Quick Check:

   Base case returns 0 to represent no contribution from null nodes [OK]

Hint: Use 0 for null nodes to avoid affecting sums [OK]

Common Mistakes:

• Returning INT_MIN which can cause incorrect sums
• Returning positive values for null nodes
• Returning 1 or -1 which are arbitrary and incorrect

3. Consider the following C code snippet for maximum path sum in a binary tree node structure. What is the output printed by printf("%d", maxSum); after calling maxPathSum(root); on the tree below?

Tree structure:
1
/ \\
2 3

typedef struct Node {
    int val;
    struct Node* left;
    struct Node* right;
} Node;

int maxSum = INT_MIN;

int maxPathSumUtil(Node* root) {
    if (!root) return 0;
    int left = maxPathSumUtil(root->left);
    int right = maxPathSumUtil(root->right);
    int maxSingle = (left > right ? left : right) + root->val;
    int maxTop = (left + right + root->val);
    if (maxTop > maxSum) maxSum = maxTop;
    return maxSingle > root->val ? maxSingle : root->val;
}

int maxPathSum(Node* root) {
    maxSum = INT_MIN;
    maxPathSumUtil(root);
    return maxSum;
}

medium

A. 3

B. 5

C. 6

D. 4

Solution

1. Step 1: Calculate max path sums for each node

   For node 2 and 3, maxSingle = 2 and 3 respectively, maxTop = 2 and 3. For root 1, left=2, right=3, maxSingle = max(2,3)+1=4, maxTop=2+3+1=6.

2. Step 2: Update maxSum and return final value

   maxSum updates to 6 at root. The function returns maxSum = 6.

3. Final Answer:

   6 -> Option C

4. Quick Check:

   Sum of path 2->1->3 = 6 [OK]

Hint: Sum path through root and children for max sum [OK]

Common Mistakes:

• Ignoring path through both children
• Returning maxSingle instead of maxSum
• Not updating global maxSum correctly

4. The following code attempts to compute the maximum path sum in a binary tree but has a bug. What is the bug?

int maxSum = INT_MIN;

int maxPathSumUtil(Node* root) {
    if (!root) return 0;
    int left = maxPathSumUtil(root->left);
    int right = maxPathSumUtil(root->right);
    int maxSingle = (left > right ? left : right) + root->val;
    int maxTop = (left + right + root->val);
    if (maxSingle > maxSum) maxSum = maxSingle;
    if (maxTop > maxSum) maxSum = maxTop;
    return maxSingle;
}

medium

A. It returns maxSingle without comparing it to root->val

B. It updates maxSum with maxSingle before maxTop, missing some max sums

C. It does not handle negative node values correctly

D. It returns maxSingle but should return maxTop

Solution

1. Step 1: Check return value correctness

   maxSingle should be max of (maxSingle, root->val) to handle negative values properly.

2. Step 2: Identify missing max comparison

   Without comparing maxSingle to root->val, the function may return a smaller sum than root's value alone.

3. Final Answer:

   It returns maxSingle without comparing it to root->val -> Option A

4. Quick Check:

   Return value must consider root->val for negatives [OK]

Hint: Always compare maxSingle with root->val before returning [OK]

Common Mistakes:

• Not handling negative values correctly
• Updating maxSum incorrectly
• Returning maxTop instead of maxSingle

5. Given a binary tree where nodes can have negative values, which approach correctly computes the maximum path sum using dynamic programming on trees?

hard

A. Use a recursive function that returns the maximum path sum including the current node and one child, update a global max with sum of node and both children, and handle negative values by comparing with zero

B. Use a recursive function that returns the maximum path sum including the current node and one child, update a global max with sum of node and both children, and handle negative values by comparing with the node's value itself

C. Use a recursive function that returns the sum of all nodes in the subtree, ignoring negative values, and update global max accordingly

D. Use a recursive function that returns the maximum path sum including the current node and both children always, without any comparison for negative values

Solution

1. Step 1: Understand handling of negative values

   Negative values require comparing max sums with the node's own value to avoid reducing sums by adding negative children.

2. Step 2: Correct recursive approach

   Return max path sum including current node and one child or node alone; update global max with sum of node and both children.

3. Final Answer:

   Use a recursive function that returns the maximum path sum including the current node and one child, update a global max with sum of node and both children, and handle negative values by comparing with the node's value itself -> Option B

4. Quick Check:

   Compare with node value to handle negatives correctly [OK]

Hint: Compare sums with node value itself to handle negatives [OK]

Common Mistakes:

• Ignoring negative values in sums
• Always adding both children without max checks
• Ignoring node's own value in comparisons