Maximum Path Sum in Binary Tree in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the definition of the Maximum Path Sum in a Binary Tree?

It is the largest sum of values obtained by any path in the binary tree. A path can start and end at any node, and must follow parent-child connections without revisiting nodes.

beginner

Why do we use recursion to solve the Maximum Path Sum problem in a binary tree?

Recursion helps explore all paths from each node by calculating maximum sums from left and right subtrees, making it easier to combine results and find the global maximum path sum.

intermediate

In the Maximum Path Sum problem, what does the helper function typically return?

It returns the maximum sum of a path starting from the current node and extending downwards to one of its children, which can be used by its parent to form larger paths.

intermediate

What is the role of a global variable in the Maximum Path Sum algorithm?

A global variable keeps track of the highest path sum found so far during recursion, ensuring the final answer is updated whenever a larger sum is found.

intermediate

How do negative node values affect the Maximum Path Sum calculation?

Negative values can reduce path sums, so the algorithm ignores paths with negative sums by comparing with zero, ensuring only positive contributions are added.

What does the Maximum Path Sum in a binary tree represent?

A The largest sum of values along any path in the tree

B The sum of all node values in the tree

C The maximum value of a single node

D The sum of values from root to leaf only

The maximum path sum is the largest sum of values along any path, which can start and end at any node.

In the recursive solution, what does the helper function return for each node?

A Maximum path sum including both left and right children

B Sum of node value only

C Maximum path sum starting from the node and extending down one child

D Minimum path sum from the node

The helper returns the max sum starting at the node and extending down one child to help parent nodes build larger paths.

Why do we compare child path sums with zero in the algorithm?

A To ignore negative sums that reduce the total path sum

B To include all sums regardless of sign

C To find the minimum path sum

D To reset the sum at each node

Negative sums are ignored by comparing with zero to avoid reducing the total path sum.

What is updated in the global variable during recursion?

A The depth of the tree

B The smallest path sum found so far

C The sum of all nodes visited

D The maximum path sum found so far

The global variable stores the maximum path sum found during traversal.

Can the maximum path sum path start and end at any node?

A No, it must be a path from left to right child

B Yes, it can start and end anywhere

C No, it must end at a leaf

D No, it must start at the root

The path can start and end at any node, as long as it follows parent-child connections.

Explain how recursion helps find the Maximum Path Sum in a binary tree.

Think about how each node's max path sum depends on its children.

Describe how negative values in nodes affect the Maximum Path Sum calculation and how the algorithm handles them.

Consider why adding a negative sum might be harmful.

Practice

1. What does the "maximum path sum" in a binary tree represent?

easy

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

B. The sum of all node values in the tree

C. The largest sum of values along any path between two nodes

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

Solution

1. Step 1: Understand the path definition

   The path can start and end at any two nodes, not necessarily root or leaf.

2. Step 2: Identify maximum sum meaning

   It is the largest 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 -> Option C

4. Quick Check:

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

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

Common Mistakes:

• Thinking it must start at root
• Confusing with sum of all nodes
• Considering only leaf nodes

2. Which of the following C function signatures is correct for a recursive function to find maximum path sum in a binary tree node defined as struct TreeNode?

easy

A. int maxPathSum(struct TreeNode* root);

B. void maxPathSum(struct TreeNode root);

C. int maxPathSum(struct TreeNode root);

D. int maxPathSum(struct TreeNode** root);

Solution

1. Step 1: Understand parameter passing for trees in C

   Binary trees are usually passed as pointers to nodes, so struct TreeNode* is correct.

2. Step 2: Check return type and parameter correctness

   Function returns int (maximum sum), and parameter is pointer to root node, so int maxPathSum(struct TreeNode* root); is correct.

3. Final Answer:

   int maxPathSum(struct TreeNode* root); -> Option A

4. Quick Check:

   Use pointer parameter and int return type [OK]

Hint: Use pointer to struct for tree nodes in C functions [OK]

Common Mistakes:

• Passing struct by value instead of pointer
• Using void return type instead of int
• Using double pointer unnecessarily

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

    1
   / \
  2   3

medium

A. 5

B. 6

C. 4

D. 3

Solution

1. Step 1: Identify all possible paths and their sums

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

2. Step 2: Find the maximum sum among these paths

   Maximum sum is 6 from path 2->1->3.

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Sum of 2 + 1 + 3 = 6 [OK]

Hint: Check paths through root connecting left and right [OK]

Common Mistakes:

• Considering only root to leaf paths
• Ignoring paths that go through root connecting children
• Choosing max node value instead of path sum

4. Consider this buggy C code snippet for maximum path sum calculation:

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

What is the main bug in this code?

medium

A. It does not update maxSum pointer correctly

B. It does not handle negative node values correctly

C. It returns maxTop instead of maxSingle

D. It uses max function without defining it

Solution

1. Step 1: Check usage of max function

   The code uses max() but C standard library does not have max function by default; it must be defined or replaced.

2. Step 2: Verify other logic parts

   Return and pointer update logic is correct; negative values handled by max comparisons.

3. Final Answer:

   It uses max function without defining it -> Option D

4. Quick Check:

   max() must be defined or replaced in C [OK]

Hint: Remember C has no built-in max function [OK]

Common Mistakes:

• Assuming max() is built-in in C
• Confusing return values with maxSum update
• Ignoring pointer usage correctness

5. You want to find the maximum path sum in a binary tree where some nodes have negative values. Which approach correctly handles negative values to find the maximum path sum?

hard

A. Use recursion to compute max path sums including negative values and update global max accordingly

B. Calculate sum of all nodes and subtract minimum negative node value

C. Only consider paths that include positive nodes and skip negative nodes completely

D. Ignore negative values by treating them as zero during recursion

Solution

1. Step 1: Understand handling of negative values in max path sum

   Negative values can reduce path sums, so recursion must consider them but choose max sums carefully.

2. Step 2: Use recursion with max comparisons to update global max

   Recursion returns max single path sum including negative values, updating global max with max of left+right+node or single path sums.

3. Final Answer:

   Use recursion to compute max path sums including negative values and update global max accordingly -> Option A

4. Quick Check:

   Include negatives but choose max sums carefully [OK]

Hint: Include negatives but pick max sums in recursion [OK]

Common Mistakes:

• Ignoring negative nodes completely
• Treating negatives as zero forcibly
• Using simple sums without max comparisons