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

Recall & Review

beginner

What is the "Maximum Path Sum" in a binary tree?

It is the largest sum of values from any path in the tree. The path can start and end at any nodes, but must follow parent-child connections.

beginner

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

Recursion helps explore all paths from each node down to its children, calculating sums and choosing the best path easily by combining results from subtrees.

intermediate

In the Maximum Path Sum problem, why do we ignore negative sums from child paths?

Negative sums reduce the total path sum, so we treat them as zero to avoid lowering the maximum sum.

intermediate

What does the helper function return in the Maximum Path Sum algorithm?

It returns the maximum sum of a path starting from the current node and extending downwards to one child, used to build larger paths.

intermediate

How do we update the global maximum path sum during recursion?

At each node, we calculate the sum of the node's value plus the best left and right child paths. If this sum is greater than the current global max, we update it.

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

A The sum of all node values in the tree

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

C The longest path length in the tree

D The smallest value in the tree

The maximum path sum is the largest sum of node values along any path in the tree.

Why do we treat negative child path sums as zero in the algorithm?

A Because negative sums increase the total path sum

B Because negative sums are not allowed in trees

C Because negative sums reduce the total path sum

D Because zero is always greater than any sum

Negative sums reduce the total path sum, so we ignore them by treating as zero.

What does the helper function return in the Maximum Path Sum algorithm?

A Minimum value in the subtree

B Maximum sum of the entire tree

C Number of nodes in the path

D Maximum sum of a path starting at the current node and going down one child

The helper returns the max sum path starting at the current node going down one child.

How is the global maximum path sum updated during recursion?

A By comparing sum of node value plus left and right child paths

B By adding all node values in the tree

C By comparing current node value only

D By counting the number of nodes

We update global max by comparing sum of node value plus best left and right child paths.

Can the maximum path in the tree start and end at any nodes?

A Yes, it can start and end anywhere following parent-child links

B No, it must start at the root

C No, it must end at a leaf node

D No, it must be a path from leftmost to rightmost node

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

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

Think about how you visit each node and use results from children.

Describe the role of ignoring negative sums in the Maximum Path Sum algorithm.

Why would adding a negative number hurt your total?

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)