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

Practice - 5 Tasks

1fill in blank

easy

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

DSA Java

List<List<Integer>> tree = new ArrayList<>();
for (int i = 0; i < n; i++) {
    tree.[1](new ArrayList<>());
}

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

Aremove

Bset

Cget

Dadd

Attempts:

3 left

💡 Hint

Common Mistakes

Using set() instead of add() causes IndexOutOfBoundsException.

Using get() or remove() does not add elements.

We use the add() method to add a new empty list for each node in the adjacency list.

2fill in blank

medium

Complete the code to add an undirected edge between nodes u and v.

DSA Java

tree.get(u).[1](v);
tree.get(v).add(u);

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

Aremove

Badd

Cset

Dclear

Attempts:

3 left

💡 Hint

Common Mistakes

Using remove() deletes elements instead of adding.

Using set() replaces existing elements, which is incorrect here.

We use add() to insert the neighbor node into the adjacency list for undirected edges.

3fill in blank

hard

Fix the error in the DFS method signature to correctly pass the parent node.

DSA Java

private int dfs(int node, int [1], List<List<Integer>> tree, int[] dp) {

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

Achild

Broot

Cparent

Dvisited

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'child' or 'root' confuses the traversal logic.

Using 'visited' as an int parameter is incorrect.

The parent parameter helps avoid revisiting the node we came from during DFS.

4fill in blank

hard

Fill both blanks to update the diameter and dp values inside DFS.

DSA Java

for (int nei : tree.get(node)) {
    if (nei != [1]) {
        int dist = dfs(nei, node, tree, dp) + 1;
        diameter = Math.max(diameter, dp[node] + dist);
        dp[node] = Math.max(dp[node], [2]);
    }
}

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

Aparent

Bdist

Cnei

Dnode

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'nei' instead of 'parent' causes infinite recursion.

Updating dp[node] with 'nei' or 'node' instead of 'dist' is wrong.

We skip the parent node to avoid cycles and update dp[node] with the maximum distance found.

5fill in blank

hard

Fill all three blanks to complete the method that returns the diameter of the tree.

DSA Java

public int treeDiameter(int n, int[][] edges) {
    List<List<Integer>> tree = new ArrayList<>();
    for (int i = 0; i < n; i++) tree.[1](new ArrayList<>());
    for (int[] edge : edges) {
        tree.get(edge[0]).[2](edge[1]);
        tree.get(edge[1]).add(edge[0]);
    }
    dp = new int[n];
    diameter = 0;
    dfs(0, -1, tree, dp);
    return [3];
}

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

Aadd

Cdiameter

Dset

Attempts:

3 left

💡 Hint

Common Mistakes

Using set() instead of add() causes errors.

Returning dp instead of diameter is incorrect.

We add empty lists for each node, add edges using add(), and return the diameter after DFS.

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 diameter definition

   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 = 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 Java code snippets correctly initializes an adjacency list for a tree with n nodes?

easy

A. ArrayList[] tree = new ArrayList[n];

B. List<Integer>[] tree = new ArrayList[n]; for(int i=0; i();

C. List<Integer> tree = new List[n];

D. ArrayList<Integer> tree = new ArrayList<>(n);

Solution

1. Step 1: Understand adjacency list initialization

   We need an array of lists, each initialized to an empty ArrayList to hold neighbors.

2. Step 2: Check each option

   List<Integer>[] tree = new ArrayList[n]; for(int i=0; i(); correctly creates an array of lists and initializes each element. Others either lack initialization or use wrong types.

3. Final Answer:

   List<Integer>[] tree = new ArrayList[n]; for(int i=0; i -> Option B

4. Quick Check:

   Array of lists with initialization [OK]

Hint: Initialize each list in array separately [OK]

Common Mistakes:

• Not initializing each list element
• Using raw List without generics
• Wrong array type declaration

3. Consider the following Java method to find the diameter of a tree. What will be the output if the tree edges are: 0-1, 1-2, 1-3?

int diameter = 0;
int dfs(int node, int parent, List<Integer>[] tree) {
  int max1 = 0, max2 = 0;
  for (int child : tree[node]) {
    if (child == parent) continue;
    int height = dfs(child, node, tree) + 1;
    if (height > max1) {
      max2 = max1;
      max1 = height;
    } else if (height > max2) {
      max2 = height;
    }
  }
  diameter = Math.max(diameter, max1 + max2);
  return max1;
}
// call dfs(0, -1, tree) and then print diameter;

medium

A. 2

B. 3

C. 1

D. 0

Solution

1. Step 1: Build the tree and understand paths

   The tree edges are 0-1, 1-2, 1-3. The longest path is from node 2 to node 0 or 3 to 0, length 2 edges.

2. Step 2: Trace DFS and diameter calculation

   DFS calculates max heights from children and updates diameter as sum of two largest heights. Here, diameter becomes 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Longest path length = 2 edges [OK]

Hint: Diameter = sum of two largest subtree heights [OK]

Common Mistakes:

• Counting nodes instead of edges
• Ignoring parent check in DFS
• Miscomputing max heights

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

int diameter = 0;
int dfs(int node, int parent, List<Integer>[] tree) {
  int max1 = 0, max2 = 0;
  for (int child : tree[node]) {
    int height = dfs(child, node, tree) + 1;
    if (height > max1) {
      max2 = max1;
      max1 = height;
    } else if (height > max2) {
      max2 = height;
    }
  }
  diameter = Math.max(diameter, max1 + max2);
  return max1;
}
// call dfs(0, -1, tree);

medium

A. Missing check to skip parent node in DFS

B. Incorrect update of diameter variable

C. Wrong return value from DFS

D. Initialization of max1 and max2 is incorrect

Solution

1. Step 1: Analyze DFS loop over children

   The code calls dfs on all children but does not skip the parent node, causing infinite recursion or stack overflow.

2. Step 2: Identify missing condition

   There should be a condition to continue if child == parent to avoid revisiting the parent.

3. Final Answer:

   Missing check to skip parent node in DFS -> Option A

4. Quick Check:

   Skip parent to prevent infinite recursion [OK]

Hint: Always skip parent node in tree DFS [OK]

Common Mistakes:

• Forgetting to skip parent node
• Misplacing diameter update
• Returning wrong height

5. You want to find the diameter of a weighted tree where edges have positive weights. Which modification to the standard diameter DFS approach is correct?

hard

A. Use BFS twice without considering weights

B. Ignore weights and count edges as 1 each

C. Add edge weights to the height calculation instead of just adding 1

D. Calculate diameter by summing all edge weights in the tree

Solution

1. Step 1: Understand weighted tree diameter

   In weighted trees, path length is sum of edge weights, not just number of edges.

2. Step 2: Modify DFS height calculation

   Instead of adding 1 for each edge, add the actual edge weight to the height returned by DFS.

3. Step 3: Update diameter similarly

   Diameter is max sum of two largest weighted heights from children.

4. Final Answer:

   Add edge weights to the height calculation instead of just adding 1 -> Option C

5. Quick Check:

   Use weights in height sums for weighted diameter [OK]

Hint: Add edge weights, not just count edges [OK]

Common Mistakes:

• Ignoring weights in diameter calculation
• Using BFS without weights
• Summing all edges instead of longest path