DP on Trees Diameter of Tree in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of diameter calculation on a simple tree

What is the output of the following JavaScript code that calculates the diameter of a tree represented as an adjacency list?

DSA Javascript

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

let diameter = 0;

function dfs(node, parent) {
  let max1 = 0, max2 = 0;
  for (const child of tree[node]) {
    if (child === parent) 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;
}

dfs(0, -1);
console.log(diameter);

A 1

B 2

C 3

D 4

💡 Hint

Trace the longest path between any two nodes in the tree.

The diameter is the longest path between any two nodes. Here, the longest path is from node 3 to node 2 through nodes 1 and 0, which has length 3 edges.

🧠 Conceptual

intermediate

Understanding the diameter update in DP on trees

In the DP approach to find the diameter of a tree, why do we update the diameter with the sum of the two largest depths from a node?

A Because the longest path can be formed by joining two longest paths from children through the current node

B Because the diameter always passes through the root node

C Because the sum of all depths gives the diameter

D Because the diameter is the maximum depth of any single subtree

💡 Hint

Think about how the longest path might pass through a node connecting two subtrees.

The diameter can be the longest path passing through a node connecting two deepest subtrees. So, summing the two largest depths from children at that node gives a candidate diameter.

🔧 Debug

advanced

Identify the error in diameter calculation code

What error does the following code produce when calculating the diameter of a tree, and why?

DSA Javascript

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

let diameter = 0;

function dfs(node, parent) {
  let max1 = 0, max2 = 0;
  for (const child of tree[node]) {
    if (child === parent) 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;
}

dfs(0, -1);
console.log(diameter);

A The code outputs 2, which is correct

B The code outputs 1, which is incorrect because it misses the longest path

C The code throws a TypeError because tree[node] is undefined

D The code outputs 0 because the diameter variable is never updated

💡 Hint

Check the longest path length between nodes in the tree.

The tree is a chain of 3 nodes (0-1-2). The longest path length is 2 edges. The code correctly calculates and outputs 2.

❓ Predict Output

advanced

Output of diameter calculation on a complex tree

What is the output of the following code that calculates the diameter of a more complex tree?

DSA Javascript

const tree = {
  0: [1, 2],
  1: [0, 3, 4],
  2: [0],
  3: [1, 5],
  4: [1],
  5: [3]
};

let diameter = 0;

function dfs(node, parent) {
  let max1 = 0, max2 = 0;
  for (const child of tree[node]) {
    if (child === parent) 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;
}

dfs(0, -1);
console.log(diameter);

A 5

B 3

C 6

D 4

💡 Hint

Find the longest path between any two nodes in the tree.

The longest path is from node 5 to node 2 through nodes 3, 1, and 0, which has length 4 edges.

🧠 Conceptual

expert

Why does the DP approach for tree diameter use two DFS traversals?

In some algorithms, the diameter of a tree is found using two DFS traversals. Why is this approach used instead of a single DFS with DP?

A Because a single DFS cannot find the diameter due to lack of memory

B Because the first DFS finds the farthest node, and the second DFS from that node finds the diameter

C Because two DFS traversals reduce the time complexity from O(n^2) to O(n log n)

D Because the diameter is always the sum of depths from two separate DFS traversals

💡 Hint

Think about how the farthest node from an arbitrary start helps find the diameter.

The two DFS method first finds the farthest node from an arbitrary node, then runs DFS from that farthest node to find the longest path, which is the 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