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

Practice - 5 Tasks

1fill in blank

easy

Complete the code to define the TreeNode class with a value and left/right children.

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number) {
    this.val = val;
    this.left = [1];
    this.right = null;
  }
}

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

Afalse

Bundefined

C0

Dnull

Attempts:

3 left

💡 Hint

Common Mistakes

Using undefined instead of null for children initialization.

Assigning 0 or false which are not valid child references.

The left and right children of a tree node are initially null when there is no child node.

2fill in blank

medium

Complete the code to calculate the maximum path sum starting from a node and going down.

DSA Typescript

function maxGain(node: TreeNode | null): number {
  if (node === null) return 0;
  const leftGain = Math.max(maxGain(node.left), [1]);
  const rightGain = Math.max(maxGain(node.right), 0);
  return node.val + Math.max(leftGain, rightGain);
}

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

A0

B1

C-1

Dnode.val

Attempts:

3 left

💡 Hint

Common Mistakes

Using 1 or -1 instead of 0 causes incorrect max gain calculation.

Using node.val instead of 0 ignores the recursive gain.

We use 0 as the minimum gain to ignore negative paths.

3fill in blank

hard

Fix the error in updating the global maximum path sum inside the recursive function.

DSA Typescript

let maxSum = Number.NEGATIVE_INFINITY;
function maxGain(node: TreeNode | null): number {
  if (node === null) return 0;
  const leftGain = Math.max(maxGain(node.left), 0);
  const rightGain = Math.max(maxGain(node.right), 0);
  const priceNewpath = node.val + leftGain + rightGain;
  maxSum = Math.max(maxSum, [1]);
  return node.val + Math.max(leftGain, rightGain);
}

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

AmaxSum

Bnode.val

CpriceNewpath

DleftGain + rightGain

Attempts:

3 left

💡 Hint

Common Mistakes

Updating maxSum with node.val only misses gains from children.

Using leftGain + rightGain misses adding node.val.

Assigning maxSum to itself causes no update.

We update maxSum with priceNewpath which is the sum of node and both gains.

4fill in blank

hard

Fill both blanks to complete the main function that returns the maximum path sum in the tree.

DSA Typescript

function maxPathSum(root: TreeNode | null): number {
  maxSum = Number.NEGATIVE_INFINITY;
  maxGain([1]);
  return [2];
}

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

Aroot

BmaxSum

Cnull

DmaxGain(root)

Attempts:

3 left

💡 Hint

Common Mistakes

Calling maxGain with null instead of root.

Returning maxGain(root) instead of maxSum.

We start recursion from root and return the global maxSum.

5fill in blank

hard

Fill all three blanks to complete the recursive function that calculates max gain and updates maxSum.

DSA Typescript

let maxSum = Number.NEGATIVE_INFINITY;
function maxGain(node: TreeNode | null): number {
  if (node === null) return [1];
  const leftGain = Math.max(maxGain(node.left), [2]);
  const rightGain = Math.max(maxGain(node.right), 0);
  const priceNewpath = node.val + leftGain + rightGain;
  maxSum = Math.max(maxSum, priceNewpath);
  return node.val + Math.max(leftGain, [3]);
}

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

A0

Bnull

CleftGain

DrightGain

Attempts:

3 left

💡 Hint

Common Mistakes

Returning null instead of 0 in base case.

Using leftGain instead of rightGain in return statement.

Return 0 for null node, ignore negative gains by comparing with 0, and return node.val plus max of left or right gain.

Practice

1. What does the "maximum path sum" in a tree represent in the context of dynamic programming on trees?

easy

A. The sum of all node values in the tree

B. The largest sum of node values along any path between two nodes in the tree

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

D. The longest path length in the tree

Solution

1. Step 1: Understand the problem definition

   The maximum path sum is about finding the path between any two nodes that yields the highest sum of node values.

2. Step 2: Differentiate from other sums

   It is not the sum of all nodes or just the max node value, but the max sum along a connected path.

3. Final Answer:

   The largest sum of node values along any path between two nodes in the tree -> Option B

4. Quick Check:

   Maximum path sum = max sum on any path [OK]

Hint: Maximum path sum is about any path, not whole tree sum [OK]

Common Mistakes:

• Confusing maximum path sum with sum of all nodes
• Thinking it is just the max node value
• Assuming path must start at root

2. Which of the following TypeScript function signatures correctly represents a recursive function to find maximum path sum in a binary tree node?

easy

A. function maxPathSum(node: TreeNode): void

B. function maxPathSum(node: number): number

C. function maxPathSum(): number

D. function maxPathSum(node: TreeNode | null): number

Solution

1. Step 1: Check parameter type

   The function must accept a TreeNode or null to handle empty nodes.

2. Step 2: Check return type

   It should return a number representing the max path sum from that node.

3. Final Answer:

   function maxPathSum(node: TreeNode | null): number -> Option D

4. Quick Check:

   Correct parameter and return type [OK]

Hint: Function must accept node or null and return number [OK]

Common Mistakes:

• Using wrong parameter type (e.g., number instead of TreeNode)
• Returning void instead of number
• Not allowing null for leaf children

3. Consider the following TypeScript code snippet for maximum path sum in a binary tree:

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

function maxPathSum(root: TreeNode | null): number {
  let maxSum = -Infinity;
  function dfs(node: TreeNode | null): number {
    if (!node) return 0;
    const left = Math.max(dfs(node.left), 0);
    const 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));

What is the output of this code?

medium

A. 3

B. 5

C. 6

D. 1

Solution

1. Step 1: Trace DFS on tree nodes

   For node 2 and 3, max path sums are 2 and 3 respectively. For root 1, left=2, right=3.

2. Step 2: Calculate maxSum updates

   maxSum updates to max(-Infinity, 1+2+3) = 6. Return value for root is 1 + max(2,3) = 4 but maxSum remains 6.

3. Final Answer:

   6 -> Option C

4. Quick Check:

   Sum of path 2->1->3 = 6 [OK]

Hint: Sum left + node + right for max path sum [OK]

Common Mistakes:

• Returning max path from root only, ignoring subtrees
• Not using Math.max with 0 to ignore negative sums
• Confusing return value with maxSum global

4. The following TypeScript code attempts to find the maximum path sum in a binary tree but has a bug:

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

What is the bug in this code?

medium

A. It does not ignore negative sums from left or right subtree

B. It returns void instead of number

C. It does not handle null root

D. It uses global variable incorrectly

Solution

1. Step 1: Analyze subtree sums usage

   The code uses left and right sums directly without ignoring negative values.

2. Step 2: Identify impact on maxSum

   Negative sums can reduce maxSum, so we must use Math.max(dfs(...), 0) to ignore negatives.

3. Final Answer:

   It does not ignore negative sums from left or right subtree -> Option A

4. Quick Check:

   Negative subtree sums must be ignored [OK]

Hint: Use Math.max(dfs(...), 0) to ignore negatives [OK]

Common Mistakes:

• Not checking for negative subtree sums
• Assuming dfs returns void
• Ignoring null root case

5. Given a binary tree where some nodes have negative values, how would you modify the dynamic programming approach to find the maximum path sum that can start and end at any node, but the path must go downwards (only from parent to child)?

hard

A. Use DFS to compute max downward path sum at each node ignoring negative sums by max(0, childSum)

B. Use BFS to find the longest path ignoring node values

C. Sum all node values and subtract minimum node value

D. Only consider paths that include the root node

Solution

1. Step 1: Understand downward path constraint

   The path must go downwards from parent to child, so use DFS to explore children.

2. Step 2: Handle negative values

   Ignore negative sums by taking max(0, childSum) to avoid reducing path sum.

3. Step 3: Calculate max path sum

   At each node, max downward path sum = node.val + max(leftChildSum, rightChildSum, 0).

4. Final Answer:

   Use DFS to compute max downward path sum at each node ignoring negative sums by max(0, childSum) -> Option A

5. Quick Check:

   Downward path + ignore negatives = DFS with max(0, childSum) [OK]

Hint: Downward path max sum uses DFS and max(0, childSum) [OK]

Common Mistakes:

• Using BFS instead of DFS
• Ignoring negative values incorrectly
• Forcing path through root only