DP on Trees Maximum Path Sum in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal of the DP on Trees Maximum Path Sum problem?

To find the maximum sum of values along any path in a tree, where a path can start and end at any nodes.

intermediate

In DP on Trees Maximum Path Sum, why do we use a post-order traversal?

Because we need to calculate the maximum path sums of child nodes before computing the parent's maximum path sum, ensuring all child information is ready.

intermediate

What does the DP state represent in the Maximum Path Sum on Trees problem?

The DP state represents the maximum path sum starting from the current node and extending down to one of its children or just the node itself.

intermediate

How do we handle negative values in nodes when calculating maximum path sums?

We ignore negative child path sums by taking the maximum of 0 and the child's path sum, so negative sums do not reduce the total.

advanced

Explain why the maximum path sum can include paths that pass through the current node connecting two children.

Because the maximum path might go from one child, through the current node, to another child, forming a path that is not just downward but passes through the node.

What traversal is best suited for DP on Trees Maximum Path Sum?

A In-order traversal

B Post-order traversal

C Pre-order traversal

D Level-order traversal

Post-order traversal processes children before the parent, which is needed to compute child path sums first.

When calculating maximum path sum at a node, what do we do with negative child sums?

A Ignore them by treating as zero

B Multiply by -1

C Subtract them

D Add them as is

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

What does the DP value returned from a node represent?

A Minimum path sum starting at the node

B Maximum path sum anywhere in the subtree

C Sum of all nodes in the subtree

D Maximum path sum starting at the node and going down

The DP value is the max sum path starting at the node and extending down to one child or none.

Can the maximum path sum include paths that do not pass through the root?

A Only if the tree is balanced

B No, it must include the root

C Yes, it can be anywhere in the tree

D Only if the tree is a binary tree

The path can start and end at any nodes, not necessarily including the root.

Which of these is NOT a valid part of the maximum path sum calculation?

A Path including cycles

B Path passing through current node connecting two children

C Path starting and ending at the same node

D Path going down to one child

Trees have no cycles, so paths cannot include cycles.

Describe the approach to solve the DP on Trees Maximum Path Sum problem step-by-step.

Think about how to combine child results and update the answer.

Explain why we consider both single child paths and paths passing through the current node connecting two children in the maximum path sum.

Consider different shapes of paths in a tree.

Practice

1. What does the "maximum path sum" in a binary tree represent?
Maximum path sum means the largest sum of node values along any path in the tree.

easy

A. The sum of node values from root to the deepest leaf

B. The sum of all node values in the tree

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

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

Solution

1. Step 1: Understand the definition of maximum path sum

   The maximum path sum is the highest sum you can get by adding node values along any path in the tree. The path can start and end at any nodes.

2. Step 2: Differentiate from other sums

   It is not just the sum of all nodes, nor the max single node, nor limited to root-to-leaf paths. It considers any path.

3. Final Answer:

   The largest sum of node values along any path in the tree -> Option D

4. Quick Check:

   Maximum path sum = largest path sum [OK]

Hint: Maximum path sum is any path's largest sum, not just root paths [OK]

Common Mistakes:

• Confusing maximum path sum with sum of all nodes
• Thinking path must start at root
• Considering only single node values

2. Which of the following Java method signatures is correct for a recursive function to find maximum path sum in a binary tree node class named TreeNode?

easy

A. int maxPathSum(TreeNode root) throws Exception

B. public int maxPathSum(TreeNode root)

C. void maxPathSum(TreeNode root)

D. public static maxPathSum(TreeNode root)

Solution

1. Step 1: Check method return type and parameters

   The method should return an int (the max sum) and accept a TreeNode parameter.

2. Step 2: Validate Java syntax

   public int maxPathSum(TreeNode root) uses correct syntax. int maxPathSum(TreeNode root) throws Exception unnecessarily throws Exception, the void version returns wrong type, the version without return type is invalid.

3. Final Answer:

   public int maxPathSum(TreeNode root) -> Option B

4. Quick Check:

   Correct method signature returns int and takes TreeNode [OK]

Hint: Method must return int and accept TreeNode parameter [OK]

Common Mistakes:

• Using void return type instead of int
• Missing return type in method signature
• Adding unnecessary throws Exception

3. Given the following Java code snippet for maximum path sum in a binary tree, what is the printed output?

class TreeNode {
  int val;
  TreeNode left, right;
  TreeNode(int v) { val = v; }
}

public class Solution {
  int maxSum = Integer.MIN_VALUE;

  public int maxPathSum(TreeNode root) {
    maxGain(root);
    return maxSum;
  }

  private int maxGain(TreeNode node) {
    if (node == null) return 0;
    int leftGain = Math.max(maxGain(node.left), 0);
    int rightGain = Math.max(maxGain(node.right), 0);
    int priceNewPath = node.val + leftGain + rightGain;
    maxSum = Math.max(maxSum, priceNewPath);
    return node.val + Math.max(leftGain, rightGain);
  }

  public static void main(String[] args) {
    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);
    Solution sol = new Solution();
    System.out.println(sol.maxPathSum(root));
  }
}

medium

A. 42

B. 35

C. 27

D. 20

Solution

1. Step 1: Trace maxGain for each node

   Calculate maxGain for leaves: 9 returns 9, 15 returns 15, 7 returns 7. For node 20: leftGain=15, rightGain=7, priceNewPath=20+15+7=42, maxSum=42. For root -10: leftGain=9, rightGain=20+15=35 (maxGain returns node.val + max(leftGain,rightGain), so for right child maxGain=35), priceNewPath at root = -10 + 9 + 35 = 34, maxSum remains 42.

2. Step 2: Determine maxSum after full traversal

   maxSum is updated to 42 at node 20, which is the maximum path sum.

3. Final Answer:

   42 -> Option A

4. Quick Check:

   Max path sum = 42 [OK]

Hint: Max path sum includes node plus max gains from left and right [OK]

Common Mistakes:

• Ignoring negative node values
• Not resetting maxSum correctly
• Confusing return value with maxSum

4. Identify the bug in this Java method for maximum path sum and select the fix:

private int maxGain(TreeNode node) {
  if (node == null) return 0;
  int leftGain = maxGain(node.left);
  int rightGain = maxGain(node.right);
  int priceNewPath = node.val + leftGain + rightGain;
  maxSum = Math.max(maxSum, priceNewPath);
  return node.val + Math.max(leftGain, rightGain);
}

medium

A. Change return type to void

B. Remove maxSum update line

C. Add Math.max(..., 0) to leftGain and rightGain to ignore negative sums

D. Return node.val + leftGain + rightGain instead

Solution

1. Step 1: Analyze handling of negative gains

   Without Math.max(..., 0), negative leftGain or rightGain reduce path sum incorrectly.

2. Step 2: Fix by ignoring negative gains

   Use int leftGain = Math.max(maxGain(node.left), 0) and similarly for rightGain to ignore negative paths.

3. Final Answer:

   Add Math.max(..., 0) to leftGain and rightGain to ignore negative sums -> Option C

4. Quick Check:

   Ignore negative gains with Math.max(..., 0) [OK]

Hint: Ignore negative child sums by max with zero [OK]

Common Mistakes:

• Not ignoring negative sums causing wrong maxSum
• Changing return type incorrectly
• Removing maxSum update line

5. You want to find the maximum path sum in a binary tree where nodes can have negative values. Which approach correctly applies dynamic programming on trees to solve this?

Choose the best description of the approach.

hard

A. Use post-order traversal; at each node, compute max gain from left and right ignoring negatives; update global max with node value plus both gains; return node value plus max gain of one side

B. Use pre-order traversal; sum all node values; return the sum as max path sum

C. Use in-order traversal; keep track of max node value only; return max node value

D. Use level-order traversal; sum values at each level; return max level sum

Solution

1. Step 1: Understand dynamic programming on trees

   Post-order traversal ensures children are processed before parent, allowing calculation of max gains from subtrees.

2. Step 2: Apply max gain logic ignoring negative sums

   At each node, calculate max gain from left and right children ignoring negatives, update global max path sum with node plus both gains, and return node plus max gain of one side for parent's use.

3. Final Answer:

   Use post-order traversal; at each node, compute max gain from left and right ignoring negatives; update global max with node value plus both gains; return node value plus max gain of one side -> Option A

4. Quick Check:

   Post-order + max gain ignoring negatives = correct DP approach [OK]

Hint: Use post-order and ignore negative gains for max path sum [OK]

Common Mistakes:

• Using wrong traversal order
• Summing all nodes instead of max path
• Ignoring negative values in gains