DP on Trees Maximum Path Sum in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the maximum path sum variable.

DSA C

int maxSum = [1];

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

A0

BINT_MIN

C1

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing maxSum to 0 causes incorrect results when all nodes are negative.

We initialize maxSum to INT_MIN to handle negative values in the tree nodes.

2fill in blank

medium

Complete the code to calculate the maximum path sum including the current node and one child.

DSA C

int leftGain = max(0, [1](node->left));

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

AmaxPathSum

BmaxSum

CmaxGain

DmaxChild

Attempts:

3 left

💡 Hint

Common Mistakes

Using maxPathSum instead of maxGain causes undefined function errors.

maxGain is the function that returns the maximum gain from a child node.

3fill in blank

hard

Fix the error in updating the global maximum path sum with the current node's value and both children.

DSA C

int priceNewPath = node->val + leftGain + max(0, [1](node->right));

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

AmaxGain

BmaxPathSum

CmaxChild

DmaxSum

Attempts:

3 left

💡 Hint

Common Mistakes

Using maxSum instead of maxGain causes type errors.

maxGain is called on the right child to get the maximum gain from the right subtree.

4fill in blank

hard

Fill both blanks to update maxSum and return the max gain for the current node.

DSA C

maxSum = max(maxSum, [1]);
return node->val + max(leftGain, [2]);

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

ApriceNewPath

BleftGain

CrightGain

DmaxSum

Attempts:

3 left

💡 Hint

Common Mistakes

Returning priceNewPath instead of node value plus max gain causes incorrect recursion.

maxSum is updated with priceNewPath, and the function returns node value plus max(leftGain, rightGain).

5fill in blank

hard

Fill all three blanks to complete the maxGain function header and base case.

DSA C

int [1](struct TreeNode* node) {
    if (node == [2]) return [3];
    // rest of the code
}

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

AmaxGain

BNULL

C0

DmaxSum

Attempts:

3 left

💡 Hint

Common Mistakes

Returning maxSum or other variables instead of 0 in base case.

maxGain is the function name, NULL is the base case for no node, and 0 is returned for no gain.