DP on Trees Maximum Path Sum in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to return the maximum path sum starting from the current node.

DSA Javascript

function maxPathDown(node) {
  if (!node) return 0;
  let left = Math.max(0, maxPathDown(node.left));
  let right = Math.max(0, maxPathDown(node.right));
  maxSum = Math.max(maxSum, node.val + left + [1]);
  return node.val + Math.max(left, right);
}

Drag options to blanks, or click blank then click option'

Aleft

Bright

C0

Dnode.val

Attempts:

3 left

💡 Hint

Common Mistakes

Forgetting to add the right child's max path sum.

Adding node.val twice.

The maximum path sum at the current node includes the node's value plus the maximum path sums from both left and right children. So we add 'right' to 'node.val + left'.

2fill in blank

medium

Complete the code to update the global maximum path sum variable.

DSA Javascript

let maxSum = -Infinity;
function maxPathDown(node) {
  if (!node) return 0;
  let left = Math.max(0, maxPathDown(node.left));
  let right = Math.max(0, maxPathDown(node.right));
  maxSum = Math.max(maxSum, node.val + left + right);
  return node.val + Math.max(left, [1]);
}

Drag options to blanks, or click blank then click option'

Aright

Bnode.val

C0

Dleft

Attempts:

3 left

💡 Hint

Common Mistakes

Returning node.val plus left plus right instead of max of left or right.

Returning node.val plus 0 always.

When returning, we choose the larger path sum between left and right to continue upwards, so we add 'right' to node.val.

3fill in blank

hard

Fix the error in the code to correctly compute the maximum path sum in the tree.

DSA Javascript

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

Drag options to blanks, or click blank then click option'

Aleft

Bnode.val

C0

Dright

Attempts:

3 left

💡 Hint

Common Mistakes

Returning node.val plus left plus right instead of max of left or right.

Returning node.val plus 0 always.

The return statement should add the node's value to the maximum of left or right path sums, so 'right' is correct here.

4fill in blank

hard

Fill both blanks to complete the function that calculates the maximum path sum including or excluding children.

DSA Javascript

function maxPathDown(node) {
  if (!node) return 0;
  let left = Math.max(0, maxPathDown(node.left));
  let right = Math.max(0, maxPathDown(node.right));
  maxSum = Math.max(maxSum, node.val + [1] + [2]);
  return node.val + Math.max(left, right);
}

Drag options to blanks, or click blank then click option'

Aleft

Bnode.val

Cright

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Adding node.val twice.

Adding zero instead of left or right.

The maximum path sum at the current node includes the node's value plus both left and right maximum path sums.

5fill in blank

hard

Fill all three blanks to complete the dictionary comprehension that maps nodes to their maximum path sums.

DSA Javascript

const maxPathSumMap = new Map();
function maxPathDown(node) {
  if (!node) return 0;
  let left = Math.max(0, maxPathDown(node.left));
  let right = Math.max(0, maxPathDown(node.right));
  maxSum = Math.max(maxSum, node.val + left + right);
  maxPathSumMap.set(node, node.val + Math.max([1], [2]));
  return node.val + Math.max([3], right);
}

Drag options to blanks, or click blank then click option'

Aleft

Bright

C0

Dnode.val

Attempts:

3 left

💡 Hint

Common Mistakes

Using node.val inside Math.max incorrectly.

Mixing up left and right in return statement.

We compare left and 0 to get the max non-negative path sum for the map, and return node.val plus max of left or right. So blanks are left, 0, left.

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