Maximum Path Sum in Binary Tree in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to define the TreeNode class with a value property.

DSA Typescript

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

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

Aval

Bvalue

CnodeVal

Dnum

Attempts:

3 left

💡 Hint

Common Mistakes

Using a different variable name than the constructor parameter.

Forgetting to assign the value to 'this.val'.

The constructor parameter is named 'val', so we assign 'this.val = val;' to store the node's value.

2fill in blank

medium

Complete the code to return the maximum path sum starting from the current 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

Bnode.val

C-Infinity

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using node.val instead of 0, which can add negative values.

Using 1 or -Infinity which are not correct for ignoring negatives.

We use 0 to ignore negative gains from child nodes, so we only add positive sums.

3fill in blank

hard

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

DSA Typescript

let maxSum = -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'

AmaxGain(node)

BpriceNewpath

Cnode.val

DleftGain + rightGain

Attempts:

3 left

💡 Hint

Common Mistakes

Using node.val alone, missing child gains.

Using maxGain(node) which causes infinite recursion.

Using leftGain + rightGain without node.val.

We update maxSum with the sum of the current node plus left and right gains, stored in priceNewpath.

4fill in blank

hard

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

DSA Typescript

function maxPathSum(root: TreeNode | null): number {
  let maxSum = -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, priceNewpath);
    return node.val + Math.max(leftGain, rightGain);
  }
  maxGain([1]);
  return [2];
}

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

Aroot

BmaxSum

Cnull

DmaxGain

Attempts:

3 left

💡 Hint

Common Mistakes

Passing null to maxGain instead of root.

Returning maxGain instead of maxSum.

Returning root instead of maxSum.

We start recursion from root and return the global maxSum after traversal.

5fill in blank

hard

Fill all three blanks to complete the function that calculates the maximum path sum using a helper and global variable.

DSA Typescript

let maxSum = -Infinity;
function maxPathSum(root: TreeNode | null): number {
  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), [2]);
    const priceNewpath = node.val + leftGain + rightGain;
    maxSum = Math.max(maxSum, priceNewpath);
    return node.val + Math.max(leftGain, rightGain);
  }
  maxGain([3]);
  return maxSum;
}

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

A0

B-Infinity

Croot

Dnull

Attempts:

3 left

💡 Hint

Common Mistakes

Using -Infinity instead of 0 for gains.

Starting recursion from null.

Not ignoring negative gains.

We ignore negative gains by comparing with 0 and start recursion from root.