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

Practice - 5 Tasks

1fill in blank

easy

Complete the code to define the TreeNode structure with integer value and pointers to left and right children.

DSA C++

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right([1]) {}
};

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

A0

BNULL

Cnullptr

Dnullptr_t

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 or NULL instead of nullptr for pointer initialization.

Forgetting to initialize right pointer.

The constructor initializes left to nullptr and right to nullptr to indicate no child nodes initially.

2fill in blank

medium

Complete the code to update the maximum path sum using the current node's value and left/right path sums.

DSA C++

maxSum = std::max(maxSum, node->val + left + [1]);

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

Aright

Bmax(left, right)

C0

Dnode->val

Attempts:

3 left

💡 Hint

Common Mistakes

Adding only one child's path sum.

Using max instead of sum of left and right.

The maximum path sum at the current node includes the node's value plus left and right path sums.

3fill in blank

hard

Fix the error in the return statement to correctly return the maximum path sum for one side plus current node's value.

DSA C++

return node->val + std::max([1], 0);

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

Aleft + right

Bleft

Cright

Dmax(left, right)

Attempts:

3 left

💡 Hint

Common Mistakes

Returning sum of left and right which is invalid for path continuation.

Not handling negative path sums.

We return the node's value plus the maximum of left or right path sums, ignoring negative sums by comparing with 0.

4fill in blank

hard

Fill both blanks to complete the recursive function that calculates max path sums from left and right children.

DSA C++

int left = std::max(0, [1](node->left));
int right = std::max(0, [2](node->right));

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

AmaxPathSumHelper

BmaxPathSum

CmaxSum

DmaxPathSumRecursive

Attempts:

3 left

💡 Hint

Common Mistakes

Using the main function name instead of helper for recursion.

Calling undefined functions.

The helper function is called recursively on left and right children to get their max path sums.

5fill in blank

hard

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

DSA C++

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

int maxPathSumHelper(TreeNode* node, int& maxSum) {
    if (!node) return 0;
    int left = std::max(0, maxPathSumHelper(node->left, maxSum));
    int right = std::max(0, maxPathSumHelper(node->right, maxSum));
    maxSum = std::max(maxSum, node->val + left + right);
    return node->val + std::max(left, right);
}

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

AINT_MIN

BmaxSum

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing maxSum to 0 which fails for all negative nodes.

Returning 0 or uninitialized variable instead of maxSum.

maxSum is initialized to INT_MIN to handle negative values, helper updates maxSum, and main returns maxSum.