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.