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

Recall & Review

beginner

What is the 'Maximum Path Sum' in a tree?

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

intermediate

Why do we use Dynamic Programming (DP) on trees for Maximum Path Sum?

Because we can break the problem into smaller subproblems: the maximum path sum starting from each child. We store results to avoid repeated work and combine them to find the global maximum.

intermediate

In DP on trees for Maximum Path Sum, what does the 'return value' of the recursive function usually represent?

It 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 node values in Maximum Path Sum on trees?

We compare the node value alone with sums including children and choose the maximum. This way, we avoid paths that reduce the sum by including negative values.

beginner

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

It keeps track of the overall maximum path sum found so far while the recursion explores all nodes.

What does the maximum path sum in a tree represent?

A The largest sum of node values on any path in the tree

B The sum of all node values in the tree

C The longest path length in the tree

D The smallest node value in the tree

The maximum path sum is the largest sum of node values on any path, not necessarily covering all nodes.

In DP on trees, what does the recursive function usually return?

A Total number of nodes in the tree

B Maximum path sum starting from the current node downwards

C Minimum node value in the subtree

D Height of the tree

The recursive function returns the maximum path sum starting at the current node and going down to one child or just the node itself.

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

A Replace negative values with zero

B Always include all nodes regardless of value

C Ignore negative values and only consider positive sums

D Compare node value alone with sums including children and choose the maximum

We choose the maximum between the node alone and sums including children to avoid reducing the total sum.

Why do we keep a global variable in the DP on Trees Maximum Path Sum algorithm?

A To store the height of the tree

B To count the number of nodes visited

C To store the overall maximum path sum found so far

D To keep track of the minimum path sum

The global variable tracks the highest path sum found anywhere in the tree during recursion.

Which of these paths is valid when calculating maximum path sum in a tree?

A A path following parent-child connections

B A path that jumps between unrelated nodes

C A path that includes cycles

D A path that skips nodes

Paths must follow parent-child connections without skipping or jumping between unrelated nodes.

Explain how dynamic programming helps find the maximum path sum in a tree.

Think about how you solve smaller parts and combine them.

Describe how to handle negative node values when computing maximum path sum on trees.

Consider when it is better to take just the node itself.

Practice

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

easy

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

B. The number of nodes in the longest path

C. The smallest sum of node values along any path

D. The sum of all node values in the tree

Solution

1. Step 1: Understand the path definition

   A path in a tree is any sequence of nodes connected by edges, not necessarily starting at the root.

2. Step 2: Define maximum path sum meaning

   The maximum path sum is the highest total value you get by adding node values along any such path.

3. Final Answer:

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

4. Quick Check:

   Maximum path sum = largest node value sum [OK]

Hint: Maximum path sum is about node values, not count or minimum [OK]

Common Mistakes:

• Confusing path length with sum
• Thinking path must start at root
• Choosing sum of all nodes instead of max path

2. Which of the following is the correct base case for a recursive function computing maximum path sum in a binary tree node?

function maxPathSum(node) {
  if (___) return 0;
  // rest of code
}

easy

A. node.value === 0

B. node.left === null && node.right === null

C. node === null

D. node === undefined

Solution

1. Step 1: Identify when recursion should stop

   When the node is empty (null), there is no path, so return 0.

2. Step 2: Check options for base case

   Only checking if node is null correctly handles leaf children and empty trees.

3. Final Answer:

   node === null -> Option C

4. Quick Check:

   Base case: node null means no path [OK]

Hint: Base case is node === null to stop recursion [OK]

Common Mistakes:

• Using node.value === 0 which is incorrect
• Checking both children null instead of node null
• Using node === undefined which is less common

3. What is the output of the following code snippet?

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function maxPathSum(root) {
  let maxSum = -Infinity;
  function dfs(node) {
    if (node === null) return 0;
    let left = Math.max(dfs(node.left), 0);
    let right = Math.max(dfs(node.right), 0);
    maxSum = Math.max(maxSum, node.val + left + right);
    return node.val + Math.max(left, right);
  }
  dfs(root);
  return maxSum;
}

const tree = new TreeNode(1, new TreeNode(2), new TreeNode(3));
console.log(maxPathSum(tree));

medium

A. 6

B. 5

C. 3

D. 1

Solution

1. Step 1: Calculate max path sums for each node

   For leaf nodes 2 and 3, max path sum is their value (2 and 3). For root 1, left=2, right=3, sum=1+2+3=6.

2. Step 2: Update maxSum and return correct values

   maxSum updates to 6 at root. Return values propagate correctly.

3. Final Answer:

   6 -> Option A

4. Quick Check:

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

Hint: Add node + max left + max right, ignore negatives [OK]

Common Mistakes:

• Forgetting to ignore negative sums
• Returning node.val + left + right instead of max(left, right)
• Confusing maxSum update with return value

4. Find the bug in this code for maximum path sum in a binary tree:

function maxPathSum(root) {
  let maxSum = -Infinity;
  function dfs(node) {
    if (!node) return 0;
    let left = dfs(node.left);
    let right = dfs(node.right);
    maxSum = Math.max(maxSum, node.val + left + right);
    return node.val + Math.max(left, right);
  }
  dfs(root);
  return maxSum;
}

medium

A. It returns maxSum before dfs call

B. It does not ignore negative sums from children

C. It uses wrong base case condition

D. It adds node.val twice in maxSum

Solution

1. Step 1: Check handling of negative child sums

   The code uses left = dfs(node.left) directly without ignoring negatives, which can reduce maxSum incorrectly.

2. Step 2: Correct approach to ignore negatives

   Should use left = Math.max(dfs(node.left), 0) and similarly for right to avoid negative paths.

3. Final Answer:

   It does not ignore negative sums from children -> Option B

4. Quick Check:

   Ignore negatives to maximize path sum [OK]

Hint: Use Math.max(childSum, 0) to skip negative paths [OK]

Common Mistakes:

• Not ignoring negative sums
• Returning before dfs call
• Wrong base case check

5. Given a binary tree where nodes can have negative values, how would you modify the maximum path sum algorithm to handle the case where all node values are negative?
Choose the best approach:

hard

A. Initialize maxSum to 0 and ignore negative sums

B. Only consider paths starting at the root

C. Return 0 if all nodes are negative

D. Initialize maxSum to -Infinity and allow paths with negative sums

Solution

1. Step 1: Understand negative values impact

   If all nodes are negative, ignoring negative sums by replacing with 0 would incorrectly return 0 instead of the max negative value.

2. Step 2: Use -Infinity initialization and allow negative sums

   Initialize maxSum to -Infinity and do not ignore negative sums completely, so the max negative node is chosen.

3. Final Answer:

   Initialize maxSum to -Infinity and allow paths with negative sums -> Option D

4. Quick Check:

   Allow negative sums to handle all-negative nodes [OK]

Hint: Use -Infinity start and allow negatives for all-negative trees [OK]

Common Mistakes:

• Ignoring negatives leads to wrong zero result
• Returning 0 when no positive path exists
• Restricting paths to root only