Maximum Path Sum in Binary Tree in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Maximum Path Sum Calculation

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

DSA C++

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

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

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

int main() {
    TreeNode* root = new TreeNode(-10);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
    std::cout << maxPathSum(root);
    return 0;
}

A 20

B 35

C 27

D 42

💡 Hint

Consider the path that includes nodes 15, 20, and 7.

The maximum path sum is 42, which comes from the path 15 -> 20 -> 7. The root node (-10) and left child (9) do not contribute to a higher sum.

🧠 Conceptual

intermediate

Understanding Path Sum Components

In the maximum path sum problem, why do we use std::max(0, left) and std::max(0, right) when calculating the maximum gain from left and right subtrees?

A To ignore negative path sums that would reduce the total sum

B To ensure the path always includes both left and right children

C To count zero as a valid node value in the path

D To handle the case when the tree is empty

💡 Hint

Think about how negative values affect the sum.

We use std::max(0, left) and std::max(0, right) to ignore any negative sums from subtrees because including a negative sum would decrease the overall path sum. This way, we only add positive contributions or zero.

🔧 Debug

advanced

Identify the Bug in Maximum Path Sum Code

What error will the following code produce when run, and why?

DSA C++

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

int maxPathSum(TreeNode* root) {
    int maxSum = 0;
    maxPathSumUtil(root, maxSum);
    return maxSum;
}

A Returns incorrect maximum path sum when all node values are negative

B Causes a segmentation fault due to null pointer dereference

C Compiles but returns zero for any input tree

D Throws a runtime error due to uninitialized variable

💡 Hint

Check the initial value of maxSum and how negative values are handled.

The initial maxSum is set to 0, so if all node values are negative, maxSum will never update to a negative value, resulting in an incorrect maximum path sum.

🚀 Application

advanced

Maximum Path Sum in a Tree with Negative and Positive Values

Given the binary tree below, what is the maximum path sum? 2 / \ -1 3 / \ -2 4

A 6

B 7

C 9

D 5

💡 Hint

Consider the path that includes nodes 2, 3, and 4.

The maximum path sum is 9, coming from the path 2 -> 3 -> 4. Other paths like 3 -> 4 sum to 7, which is lower.

❓ Predict Output

expert

Output of Maximum Path Sum with Single Node Negative Tree

What is the output of the following code when the tree has a single node with value -5?

DSA C++

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

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

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

int main() {
    TreeNode* root = new TreeNode(-5);
    std::cout << maxPathSum(root);
    return 0;
}

A 0

B -5

C 5

D INT_MIN

💡 Hint

The maximum path sum can be a single node value if all others are negative or absent.

Since the tree has only one node with value -5, the maximum path sum is -5.