Maximum Path Sum in Binary Tree in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Maximum Path Sum Calculation

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

A 27

B 35

C 42

D 20

💡 Hint

Consider the path that includes the root's right subtree and its children.

The maximum path sum is 42, coming from the path 15 -> 20 -> 7. The root's value -10 is not included because it reduces the sum. The path 15 + 20 + 7 = 42 is the highest sum path in the tree.

🧠 Conceptual

intermediate

Understanding Maximum Path Sum Concept

Which statement best describes the maximum path sum in a binary tree?

A It is the largest sum of values from any path between two nodes, which may or may not include the root.

B It is the sum of all node values in the tree.

C It is the largest sum of values from any path starting at the root and ending at a leaf.

D It is the largest sum of values from any path that must include the root node.

💡 Hint

Think about paths that can start and end anywhere in the tree.

The maximum path sum is the largest sum of values from any path between two nodes in the tree. The path can start and end at any nodes and does not have to include the root or a leaf.

🔧 Debug

advanced

Identify the Error in Maximum Path Sum Code

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

DSA Typescript

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

A Returns 0

B Returns 4

C Returns 1

D Returns 3

💡 Hint

Check how negative values affect the path sums.

The code does not ignore negative sums from children, so it includes negative values in the path sum. The maximum path sum is 4 from path 3 + 1, ignoring the negative left child.

❓ Predict Output

advanced

Output of Maximum Path Sum with Negative Nodes

What is the output of this TypeScript code calculating maximum path sum in a tree with 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 tree = new TreeNode(-3);
console.log(maxPathSum(tree));

A -Infinity

B 0

C 3

D -3

💡 Hint

Consider that the tree has only one node with a negative value.

The maximum path sum is -3 because the only node has value -3. The code returns the node value since no positive gains from children exist.

🧠 Conceptual

expert

Why Use Math.max with 0 in Maximum Path Sum DFS?

Why does the maximum path sum algorithm use Math.max(dfs(child), 0) when calculating left and right gains?

A To ignore negative path sums from children that would reduce the total sum.

B To ensure the path always includes both children.

C To convert all negative values to zero permanently in the tree.

D To count only leaf nodes in the path sum calculation.

💡 Hint

Think about how negative values affect the sum of a path.

Using Math.max with 0 ignores negative sums from children, preventing them from decreasing the total path sum. This ensures the path sum only includes positive contributions.

Practice

1. What does the "Maximum Path Sum in Binary Tree" problem ask you to find?

easy

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

B. The longest path length in the tree

C. The sum of all node values in the tree

D. The minimum value node in the tree

Solution

1. Step 1: Understand the problem goal

   The problem asks for the maximum sum of values along any path in the binary tree, where a path can start and end at any nodes.

2. Step 2: Differentiate from other tree sums

   This is different from longest path or total sum; it focuses on the maximum sum achievable on any path.

3. Final Answer:

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

4. Quick Check:

   Maximum path sum = highest node value sum [OK]

Hint: Focus on sums along paths, not lengths or totals [OK]

Common Mistakes:

• Confusing path sum with longest path length
• Summing all nodes instead of a path
• Looking for minimum instead of maximum

2. Which TypeScript function signature correctly represents a function to find maximum path sum in a binary tree node?

easy

A. function maxPathSum(root: number[]): number

B. function maxPathSum(root: TreeNode | null): number

C. function maxPathSum(root: string): string

D. function maxPathSum(root: TreeNode): void

Solution

1. Step 1: Identify correct parameter type

   The function should accept a binary tree node or null, so TreeNode | null is correct.

2. Step 2: Identify correct return type

   The function returns a number representing the maximum path sum, so return type is number.

3. Final Answer:

   function maxPathSum(root: TreeNode | null): number -> Option B

4. Quick Check:

   Input: TreeNode or null, Output: number [OK]

Hint: Function input is tree node or null, output is number [OK]

Common Mistakes:

• Using array or string instead of TreeNode
• Returning void instead of number
• Not allowing null as input

3. Given the following TypeScript code, what is the output?

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number, 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 helper(node: TreeNode | null): number {
    if (!node) return 0;
    const left = Math.max(helper(node.left), 0);
    const right = Math.max(helper(node.right), 0);
    maxSum = Math.max(maxSum, node.val + left + right);
    return node.val + Math.max(left, right);
  }
  helper(root);
  return maxSum;
}

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

medium

A. 3

B. 5

C. 1

D. 6

Solution

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

   Node 2 and 3 have no children, so max path sums are 2 and 3. For root 1, left=2, right=3, total=1+2+3=6.

2. Step 2: Determine maximum path sum

   Maximum path sum is max of all nodes' sums: max(2,3,6) = 6.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   Sum(1+2+3) = 6 [OK]

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

Common Mistakes:

• Ignoring zero floor for negative sums
• Returning sum of only root and one child
• Confusing return value with maxSum variable

4. Identify the bug in this TypeScript function for maximum path sum:

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

medium

A. Returns node.val + min(left, right) instead of max

B. helper function missing base case

C. maxSum initialized to 0 instead of -Infinity

D. Does not call helper on root

Solution

1. Step 1: Check maxSum initialization

   maxSum initialized to 0 can cause wrong result if all node values are negative.

2. Step 2: Correct initialization for negative values

   Initialize maxSum to -Infinity to handle negative node values correctly.

3. Final Answer:

   maxSum initialized to 0 instead of -Infinity -> Option C

4. Quick Check:

   maxSum must start at -Infinity for negative nodes [OK]

Hint: Initialize maxSum to -Infinity to handle negatives [OK]

Common Mistakes:

• Starting maxSum at 0 causes wrong max for negative trees
• Forgetting base case returns 0
• Using min instead of max for return

5. Given a binary tree with nodes: root= -10, left=9, right=20, right.left=15, right.right=7, what is the maximum path sum?

hard

A. 42

B. 35

C. 27

D. 20

Solution

1. Step 1: Calculate max path sums for subtrees

   Right subtree max path: 15 + 20 + 7 = 42. Left subtree max is 9. Root is -10.

2. Step 2: Determine overall max path sum

   Max path sum is max of 42 (right subtree path), 9 (left), and paths including root. The max is 42.

3. Final Answer:

   42 -> Option A

4. Quick Check:

   Sum(15+20+7) = 42 [OK]

Hint: Check all subtree sums including root, pick max [OK]

Common Mistakes:

• Ignoring path through both children and root
• Choosing sum of root and one child only
• Not considering negative root value impact