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

Practice - 5 Tasks

1fill in blank

easy

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

DSA Javascript

const n = 5;
const edges = [[1, 2], [1, 3], [3, 4], [3, 5]];
const graph = Array.from({ length: n + 1 }, () => [1]);

console.log(graph);

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

A[]

B{}

C0

Dnull

Attempts:

3 left

💡 Hint

Common Mistakes

Using an object {} instead of an array for adjacency list.

Initializing with null or 0 which are not iterable.

We use an array of empty arrays to represent adjacency lists for each node.

2fill in blank

medium

Complete the code to add edges to the adjacency list.

DSA Javascript

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

console.log(graph);

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

Aedges

Bu

Cgraph

Dv

Attempts:

3 left

💡 Hint

Common Mistakes

Adding u to u's own adjacency list.

Using the whole graph or edges array instead of node v.

We add node v to u's adjacency list and vice versa to represent an undirected edge.

3fill in blank

hard

Fix the error in the DFS function to correctly compute the diameter.

DSA Javascript

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

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

Achild

Bnode

Cparent

Ddiameter

Attempts:

3 left

💡 Hint

Common Mistakes

Skipping the current node instead of the parent.

Not skipping any node causing infinite loops.

We skip the parent node to avoid revisiting it and causing infinite recursion.

4fill in blank

hard

Fill both blanks to start DFS from node 1 and print the diameter.

DSA Javascript

let diameter = 0;

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

dfs([1], [2]);
console.log(diameter);

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

A1

B0

C-1

Dnull

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 as parent which is a valid node and causes wrong skipping.

Using null which is not a number and may cause errors.

We start DFS from node 1 and use -1 as parent since it has no parent.

5fill in blank

hard

Fill all three blanks to implement the diameter calculation using DFS and print the result.

DSA Javascript

const n = 4;
const edges = [[1, 2], [2, 3], [2, 4]];
const graph = Array.from({ length: n + 1 }, () => [1]);
for (const [u, v] of edges) {
  graph[u].push(v);
  graph[v].push(u);
}

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

dfs([2], [3]);
console.log(diameter);

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

A[]

B1

C-1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing graph with null or 0 instead of empty arrays.

Starting DFS from node 0 which does not exist.

Using 0 as parent which is a valid node.

Initialize graph with empty arrays, start DFS from node 1 with parent -1 to compute diameter.

Practice

1. What does the diameter of a tree represent in graph theory?

easy

A. The number of leaf nodes in the tree

B. The number of nodes in the tree

C. The height of the tree from the root

D. The longest path between any two nodes in the tree

Solution

1. Step 1: Understand the definition of diameter

   The diameter is the longest path between any two nodes in a tree, not just from the root.

2. Step 2: Differentiate from other tree properties

   Height is the longest path from root to leaf, number of nodes and leaves are counts, not paths.

3. Final Answer:

   The longest path between any two nodes in the tree -> Option D

4. Quick Check:

   Diameter = Longest path [OK]

Hint: Diameter is longest path between any two nodes [OK]

Common Mistakes:

• Confusing diameter with height
• Thinking diameter counts nodes instead of path length
• Assuming diameter is from root only

2. Which of the following JavaScript code snippets correctly initializes an adjacency list for a tree with 3 nodes?

easy

A. const tree = {0: [1, 2], 1: [0], 2: [0]};

B. const tree = [[1, 2], [], []];

C. const tree = {0: 1, 1: 2, 2: 0};

D. const tree = [0, 1, 2];

Solution

1. Step 1: Understand adjacency list structure

   An adjacency list maps each node to an array of its connected nodes.

2. Step 2: Check each option

   const tree = {0: [1, 2], 1: [0], 2: [0]}; uses an object with arrays for neighbors, correct for adjacency list. const tree = [[1, 2], [], []]; misses reverse edges from 1 and 2 to 0. const tree = {0: 1, 1: 2, 2: 0}; maps nodes to single nodes, not arrays. const tree = [0, 1, 2]; is just a list of nodes, no edges.

3. Final Answer:

   const tree = {0: [1, 2], 1: [0], 2: [0]}; -> Option A

4. Quick Check:

   Adjacency list = Object with arrays [OK]

Hint: Adjacency list maps nodes to arrays of neighbors [OK]

Common Mistakes:

• Using single values instead of arrays for neighbors
• Confusing arrays of nodes with adjacency lists
• Not including reverse edges in undirected tree

3. Consider the following JavaScript code to find the diameter of a tree represented as an adjacency list. What will be the output?

const tree = {0: [1], 1: [0, 2, 3], 2: [1], 3: [1, 4], 4: [3]};
let maxDiameter = 0;
function dfs(node, parent) {
  let max1 = 0, max2 = 0;
  for (const child of tree[node]) {
    if (child === parent) continue;
    const length = dfs(child, node) + 1;
    if (length > max1) {
      max2 = max1;
      max1 = length;
    } else if (length > max2) {
      max2 = length;
    }
  }
  maxDiameter = Math.max(maxDiameter, max1 + max2);
  return max1;
}
dfs(0, -1);
console.log(maxDiameter);

medium

A. 3

B. 5

C. 4

D. 2

Solution

1. Step 1: Trace DFS to find longest paths

   Starting at node 0, DFS explores children. The longest path is from node 2 to node 4 passing through 1 and 3, length 3 edges.

2. Step 2: Calculate diameter from max1 + max2

   At node 1, max1=2 (to node 4), max2=1 (to node 2), sum=3 edges. At node 3, max1=1 (to node 4), max2=0, sum=1. The maximum sum found is 3 edges.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Longest path length = 3 edges [OK]

Hint: Diameter = sum of two longest child paths at any node [OK]

Common Mistakes:

• Counting nodes instead of edges for diameter
• Ignoring the second longest path in calculation
• Not skipping parent node in DFS

4. The following code attempts to compute the diameter of a tree but has a bug. What is the bug?

const tree = {0: [1], 1: [0, 2], 2: [1]};
let maxDiameter = 0;
function dfs(node) {
  let max1 = 0, max2 = 0;
  for (const child of tree[node]) {
    const length = dfs(child) + 1;
    if (length > max1) {
      max2 = max1;
      max1 = length;
    } else if (length > max2) {
      max2 = length;
    }
  }
  maxDiameter = Math.max(maxDiameter, max1 + max2);
  return max1;
}
dfs(0);
console.log(maxDiameter);

medium

A. Tree adjacency list is incorrectly defined

B. maxDiameter is not updated correctly

C. Missing parent check causes infinite recursion

D. DFS does not return correct path length

Solution

1. Step 1: Identify missing parent check in DFS

   The DFS function does not skip the parent node, causing it to revisit the previous node endlessly, leading to infinite recursion.

2. Step 2: Understand impact of missing parent check

   Without skipping the parent, the DFS calls loop back and forth between nodes, never terminating.

3. Final Answer:

   Missing parent check causes infinite recursion -> Option C

4. Quick Check:

   Always skip parent node in DFS to avoid loops [OK]

Hint: Always pass and skip parent node in DFS [OK]

Common Mistakes:

• Not passing parent node in DFS
• Assuming tree edges are directed
• Updating maxDiameter incorrectly

5. You have a tree with weighted edges represented as an adjacency list: {0: [[1, 3], [2, 5]], 1: [[0, 3], [3, 4]], 2: [[0, 5]], 3: [[1, 4]]}. How would you modify the diameter calculation to find the longest weighted path?

hard

A. Ignore weights and count edges only

B. Add edge weights to the DFS return values and update maxDiameter accordingly

C. Use BFS instead of DFS without weights

D. Sum all weights in the tree and divide by number of edges

Solution

1. Step 1: Incorporate edge weights in DFS

   Modify DFS to add the weight of each edge when calculating path lengths instead of just adding 1.

2. Step 2: Update maxDiameter with weighted sums

   At each node, update maxDiameter with the sum of the two longest weighted paths found among children.

3. Final Answer:

   Add edge weights to the DFS return values and update maxDiameter accordingly -> Option B

4. Quick Check:

   Weighted diameter needs weighted path sums [OK]

Hint: Add weights to path lengths in DFS for weighted diameter [OK]

Common Mistakes:

• Ignoring weights and counting edges only
• Using BFS without weights for diameter
• Summing all weights instead of longest path