DP on Trees Diameter of Tree in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the adjacency list for the tree.

DSA Typescript

const adj: number[][] = Array(n).fill(0).map(() => []);

for (const [u, v] of edges) {
  adj[u].push([1]);
  adj[v].push(u);
}

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

Au

Bv

Cedges

Dadj

Attempts:

3 left

💡 Hint

Common Mistakes

Adding u to u's adjacency list instead of v.

Using the whole edges array instead of a single node.

We add node v to the adjacency list of u to represent the edge u-v.

2fill in blank

medium

Complete the code to perform DFS and update the diameter.

DSA Typescript

function dfs(node: number, parent: number): number {
  let max1 = 0, max2 = 0;
  for (const child of adj[node]) {
    if (child === [1]) continue;
    const depth = dfs(child, node) + 1;
    if (depth > max1) {
      max2 = max1;
      max1 = depth;
    } else if (depth > max2) {
      max2 = depth;
    }
  }
  diameter = Math.max(diameter, max1 + max2);
  return max1;
}

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

Aparent

Bnode

Cchild

Ddiameter

Attempts:

3 left

💡 Hint

Common Mistakes

Skipping the wrong node.

Not skipping any node causing infinite recursion.

We skip the parent node to avoid revisiting the node we came from.

3fill in blank

hard

Fix the error in the diameter update line to correctly compute the diameter.

DSA Typescript

diameter = Math.max(diameter, [1] + max2);

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

Adepth

Bmax2

Cmax1

Dnode

Attempts:

3 left

💡 Hint

Common Mistakes

Using only one depth instead of sum of two.

Using wrong variables causing incorrect diameter.

The diameter is updated by the sum of the two longest depths max1 and max2.

4fill in blank

hard

Fill both blanks to complete the function that computes the diameter of the tree.

DSA Typescript

function treeDiameter(n: number, edges: number[][]): number {
  const adj: number[][] = Array(n).fill(0).map(() => []);
  for (const [u, v] of edges) {
    adj[u].push(v);
    adj[v].push(u);
  }
  let diameter = 0;
  function dfs(node: number, parent: number): number {
    let max1 = 0, max2 = 0;
    for (const child of adj[node]) {
      if (child === [1]) continue;
      const depth = dfs(child, node) + 1;
      if (depth > max1) {
        max2 = max1;
        max1 = depth;
      } else if (depth > max2) {
        max2 = depth;
      }
    }
    diameter = Math.max(diameter, max1 + [2]);
    return max1;
  }
  dfs(0, -1);
  return diameter;
}

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

Aparent

Bnode

Cmax2

Dmax1

Attempts:

3 left

💡 Hint

Common Mistakes

Not skipping parent causing infinite recursion.

Using wrong variables in diameter update.

Skip the parent node and update diameter with sum of max1 and max2 depths.

5fill in blank

hard

Fill all three blanks to complete the code that calculates the diameter of a tree using DFS.

DSA Typescript

function treeDiameter(n: number, edges: number[][]): number {
  const adj: number[][] = Array(n).fill(0).map(() => []);
  for (const [u, v] of edges) {
    adj[u].push(v);
    adj[v].push(u);
  }
  let diameter = 0;
  function dfs(node: number, parent: number): number {
    let max1 = 0, max2 = 0;
    for (const child of adj[node]) {
      if (child === [1]) continue;
      const depth = dfs(child, [2]) + 1;
      if (depth > max1) {
        max2 = max1;
        max1 = depth;
      } else if (depth > max2) {
        max2 = depth;
      }
    }
    diameter = Math.max(diameter, max1 + max2);
    return [3];
  }
  dfs(0, -1);
  return diameter;
}

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

Aparent

Bnode

Cmax1

Dmax2

Attempts:

3 left

💡 Hint

Common Mistakes

Passing wrong parent in recursion.

Returning wrong depth value.

Skip parent node, pass current node as parent in recursion, and return max1 depth.