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.

Practice

1. What does the term Maximum Path Sum in a binary tree mean?

easy

A. The sum of all node values in the tree

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

C. The maximum value of a single node in the tree

D. The sum of values from root to the deepest leaf only

Solution

1. Step 1: Understand the path definition

   A path in a binary tree can start and end at any nodes, not necessarily root or leaf.

2. Step 2: Define maximum path sum

   It is the highest 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 in the tree -> Option B

4. Quick Check:

   Maximum path sum means highest sum on any path [OK]

Hint: Maximum path sum is any path, not just root to leaf [OK]

Common Mistakes:

• Confusing maximum path sum with sum of all nodes
• Thinking path must start at root
• Considering only leaf nodes for path ends

2. Which of the following C++ function signatures is correct for a helper function that returns the maximum path sum starting from a given node in a binary tree?

easy

A. int maxPathSumHelper(TreeNode* root, int& maxSum);

B. void maxPathSumHelper(TreeNode root, int maxSum);

C. int maxPathSumHelper(TreeNode root);

D. int maxPathSumHelper(TreeNode* root);

Solution

1. Step 1: Understand parameter passing

   The function needs to update maxSum globally, so it must be passed by reference.

2. Step 2: Check pointer usage

   TreeNode* is used to pass node pointers, not objects directly.

3. Final Answer:

   int maxPathSumHelper(TreeNode* root, int& maxSum); -> Option A

4. Quick Check:

   Use pointer and reference for maxSum [OK]

Hint: Pass maxSum by reference and node as pointer [OK]

Common Mistakes:

• Passing TreeNode by value instead of pointer
• Not passing maxSum by reference
• Using void return type instead of int

3. Consider the following binary tree:

    1
   / \
  2   3

What is the maximum path sum returned by the standard algorithm?

medium

A. 3

B. 5

C. 4

D. 6

Solution

1. Step 1: Calculate path sums including root

   Paths: 2->1->3 sum = 6, 2->1 sum = 3, 1->3 sum = 4.

2. Step 2: Identify maximum sum

   The maximum path sum is 6 from path 2->1->3.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   2+1+3 = 6 [OK]

Hint: Check all paths including both children and root [OK]

Common Mistakes:

• Considering only root-to-leaf paths
• Ignoring paths passing through root
• Adding only one child value

4. Given this buggy code snippet for maximum path sum, what is the main error?

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

What is the bug?

medium

A. It does not ignore negative path sums

B. It returns sum of both children instead of max child

C. It updates maxSum incorrectly

D. It does not handle null root

Solution

1. Step 1: Analyze negative path sums handling

   The code adds left and right directly without ignoring negative sums, which can reduce maxSum.

2. Step 2: Correct approach for negatives

   Should use max(0, left) and max(0, right) to ignore negative sums.

3. Final Answer:

   It does not ignore negative path sums -> Option A

4. Quick Check:

   Negative sums must be ignored to maximize path sum [OK]

Hint: Use max(0, child) to ignore negative sums [OK]

Common Mistakes:

• Adding negative child sums reduces maxSum
• Returning sum of both children instead of max child
• Not checking for null root

5. Given the binary tree below, what is the maximum path sum?

       -10
       /  \
      9   20
          / \
         15  7

Choose the correct maximum path sum.

hard

A. 27

B. 35

C. 42

D. 15

Solution

1. Step 1: Calculate max path sums for subtrees

   Left subtree max path sum is 9. Right subtree max path sum includes 20 + 15 + 7 = 42.

2. Step 2: Consider paths through root

   Path through root: -10 + max(0,9) + max(0,15+20+7) = -10 + 9 + 42 = 41, less than 42.

3. Step 3: Identify maximum path sum

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

4. Final Answer:

   42 -> Option C

5. Quick Check:

   15+20+7 = 42 [OK]

Hint: Check all subtree sums and paths through root [OK]

Common Mistakes:

• Including negative root value in max path sum
• Ignoring paths not passing through root
• Adding left and right children without max(0, val)