DP on Trees Maximum Path Sum in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Maximum Path Sum in a Simple Binary Tree

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

DSA Javascript

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) 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 root = new TreeNode(1, new TreeNode(2), new TreeNode(3));
console.log(maxPathSum(root));

A 6

B 5

C 3

D 1

💡 Hint

Consider the path that includes both left and right children plus the root.

The maximum path sum is 2 + 1 + 3 = 6. The code calculates the maximum sum of any path in the tree, which can include both children and the root node.

❓ Predict Output

intermediate

Maximum Path Sum with Negative Values

What will be the output of this code when the tree contains negative values?

DSA Javascript

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) 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 root = new TreeNode(-10, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));
console.log(maxPathSum(root));

A 35

B 42

C 27

D -10

💡 Hint

The maximum path sum can skip negative branches by using Math.max with 0.

The maximum path sum is 15 + 20 + 7 = 42. The root's left child (9) is less than this sum, and the root's value (-10) is negative, so the path with 20 and its children gives the maximum sum.

🔧 Debug

advanced

Identify the Error in Maximum Path Sum Calculation

What error will this code produce when calculating the maximum path sum?

DSA Javascript

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) 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;
}

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

A Returns -6

B Returns -1

C Returns -Infinity

D TypeError: Cannot read property 'val' of null

💡 Hint

Check how negative values are handled in the recursion.

The code does not ignore negative sums, so left and right can be negative, reducing the path sum. The maximum path sum calculated is -2 + (-1) + (-3) = -6.

🧠 Conceptual

advanced

Understanding the Role of Returning Values in DFS

In the maximum path sum algorithm on trees, why do we return node.val + Math.max(left, right) from the DFS function instead of node.val + left + right?

A Because the algorithm only considers leaf nodes for the maximum path sum.

B Because adding both left and right would count the node twice in the path sum.

C Because returning both left and right sums would cause a syntax error.

D Because the path can only continue in one direction (left or right) from the current node upwards.

💡 Hint

Think about the path shape when moving up the tree.

The path can branch at the current node including both children, but when returning to the parent, the path can only continue through one child to avoid cycles. Hence, we return the max of left or right plus the node's value.

🚀 Application

expert

Maximum Path Sum in a Tree with Multiple Branches

Given the following tree structure, what is the maximum path sum computed by the algorithm? Tree: 10 / \ 2 10 / \ \ 20 1 -25 / \ 3 4

DSA Javascript

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) 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 root = new TreeNode(10,
  new TreeNode(2, new TreeNode(20), new TreeNode(1)),
  new TreeNode(10, null, new TreeNode(-25, new TreeNode(3), new TreeNode(4)))
);
console.log(maxPathSum(root));

A 37

B 48

C 42

D 35

💡 Hint

Consider the path that includes 20, 2, 10, and the right 10 node.

The maximum path sum is 20 + 2 + 10 + 10 = 42. The negative node -25 and its children reduce the sum, so they are ignored. The algorithm picks the path 20 -> 2 -> 10 -> 10 for the maximum sum.

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