DP on Trees Maximum Path Sum in DSA Typescript - 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 TypeScript code that calculates the maximum path sum in a binary tree?

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : 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 root = new TreeNode(1, new TreeNode(2), new TreeNode(3));
console.log(maxPathSum(root));

A 6

B 5

C 3

D 1

💡 Hint

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

The maximum path sum is 2 + 1 + 3 = 6. The function calculates the max sum including left and right subtrees and updates the global max.

❓ Predict Output

intermediate

Maximum Path Sum with Negative Values

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

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : 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 root = new TreeNode(-10, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));
console.log(maxPathSum(root));

A -10

B 35

C 20

D 42

💡 Hint

Consider the path that includes nodes 15, 20, and 7.

The maximum path sum is 15 + 20 + 7 = 42. The function ignores negative paths by using Math.max with 0.

🔧 Debug

advanced

Identify the Error in Maximum Path Sum Implementation

What error will this code produce when run?

DSA Typescript

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

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

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

A Stack overflow error due to infinite recursion

B Output is 3 (only root value)

C No error, output is 6

D Output is 7 (incorrect max sum)

💡 Hint

Check how negative values are handled in recursion.

No runtime error and output is 6 (correct for this positive tree). However, the code has a logical bug: it does not ignore negative subtree sums (missing Math.max(..., 0)), which would cause incorrect results on trees with negatives.

🧠 Conceptual

advanced

Understanding the Role of Math.max in DP on Trees

Why do we use Math.max(dfs(node.left), 0) in the maximum path sum calculation?

A To ignore negative path sums and only add positive contributions

B To ensure the recursion terminates properly

C To count the number of nodes in the path

D To double the value of the node if positive

💡 Hint

Think about how negative values affect sums.

Using Math.max with 0 ignores negative sums, preventing them from reducing the total path sum.

🚀 Application

expert

Maximum Path Sum in a Tree with Multiple Branches

Given the following tree structure, what is the maximum path sum?

DSA Typescript

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

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

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

console.log(maxPathSum(root));

A 55

B 42

C 48

D 60

💡 Hint

Focus on the path that includes nodes 20, 2, 10, and 10.

The maximum path sum is 42 from the path 20 -> 2 -> 10 -> 10. The negative branch (-25) is ignored due to Math.max with 0.