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.