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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Diameter Calculation on a Simple Tree

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

DSA Java

import java.util.*;

public class TreeDiameter {
    static List<List<Integer>> tree = new ArrayList<>();
    static int diameter = 0;

    public static int dfs(int node, int parent) {
        int max1 = 0, max2 = 0;
        for (int child : tree.get(node)) {
            if (child == parent) continue;
            int height = dfs(child, node);
            if (height > max1) {
                max2 = max1;
                max1 = height;
            } else if (height > max2) {
                max2 = height;
            }
        }
        diameter = Math.max(diameter, max1 + max2);
        return max1 + 1;
    }

    public static void main(String[] args) {
        int n = 5;
        for (int i = 0; i < n; i++) tree.add(new ArrayList<>());
        tree.get(0).add(1); tree.get(1).add(0);
        tree.get(1).add(2); tree.get(2).add(1);
        tree.get(1).add(3); tree.get(3).add(1);
        tree.get(3).add(4); tree.get(4).add(3);

        dfs(0, -1);
        System.out.println(diameter);
    }
}

A 2

B 3

C 5

D 4

💡 Hint

Think about the longest path between any two nodes in the tree.

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

🧠 Conceptual

intermediate

Understanding Diameter Calculation Logic

In the diameter calculation using DFS on a tree, why do we keep track of the two longest heights from the children of a node?

A Because the diameter may pass through the current node connecting two longest paths from its children.

B Because we need to count the number of children nodes for the diameter.

C Because the diameter is always the longest height from a single child.

D Because the diameter is the sum of all heights of children nodes.

💡 Hint

Think about the longest path that can pass through a node connecting two subtrees.

The diameter can be the longest path passing through a node, which is the sum of the two longest heights from its children. Tracking two longest heights helps find this path.

🔧 Debug

advanced

Identify the Error in Diameter Calculation Code

What error will the following code produce when calculating the diameter of a tree?

DSA Java

import java.util.*;

public class TreeDiameter {
    static List<List<Integer>> tree = new ArrayList<>();
    static int diameter = 0;

    public static int dfs(int node, int parent) {
        int max1 = 0, max2 = 0;
        for (int child : tree.get(node)) {
            if (child == parent) continue;
            int height = dfs(child, node);
            if (height > max1) {
                max2 = max1;
                max1 = height;
            } else if (height > max2) {
                max2 = height;
            }
        }
        diameter = Math.max(diameter, max1 + max2);
        return max1 + 1;
    }

    public static void main(String[] args) {
        int n = 3;
        for (int i = 0; i < n; i++) tree.add(new ArrayList<>());
        tree.get(0).add(1); tree.get(1).add(0);
        tree.get(1).add(2); tree.get(2).add(1);
        tree.get(2).add(3); tree.get(3).add(2);

        dfs(0, -1);
        System.out.println(diameter);
    }
}

A IndexOutOfBoundsException at tree.get(3)

B StackOverflowError due to infinite recursion

C Prints incorrect diameter value 2

D Compilation error due to missing semicolon

💡 Hint

Check the size of the tree list and the indices accessed.

The code initializes tree with size 3 but tries to access tree.get(3), which is out of bounds causing IndexOutOfBoundsException.

❓ Predict Output

advanced

Output of Diameter Calculation on a Star-Shaped Tree

What is the output of the following Java code that calculates the diameter of a star-shaped tree with 5 nodes?

DSA Java

import java.util.*;

public class TreeDiameter {
    static List<List<Integer>> tree = new ArrayList<>();
    static int diameter = 0;

    public static int dfs(int node, int parent) {
        int max1 = 0, max2 = 0;
        for (int child : tree.get(node)) {
            if (child == parent) continue;
            int height = dfs(child, node);
            if (height > max1) {
                max2 = max1;
                max1 = height;
            } else if (height > max2) {
                max2 = height;
            }
        }
        diameter = Math.max(diameter, max1 + max2);
        return max1 + 1;
    }

    public static void main(String[] args) {
        int n = 5;
        for (int i = 0; i < n; i++) tree.add(new ArrayList<>());
        tree.get(0).add(1); tree.get(1).add(0);
        tree.get(0).add(2); tree.get(2).add(0);
        tree.get(0).add(3); tree.get(3).add(0);
        tree.get(0).add(4); tree.get(4).add(0);

        dfs(0, -1);
        System.out.println(diameter);
    }
}

A 1

B 4

C 2

D 3

💡 Hint

In a star-shaped tree, the longest path is between two leaf nodes through the center.

The diameter is the longest path between two leaves through the center node 0, which has length 2 edges.

🚀 Application

expert

Maximum Diameter After Adding One Edge

Given a tree with 6 nodes and edges [[0,1],[1,2],[1,3],[3,4],[3,5]], if you add one edge connecting any two existing nodes (not already connected), what is the maximum possible diameter of the resulting graph?

A 5

B 4

C 6

D 3

💡 Hint

Adding an edge can create a cycle and may reduce the diameter.

The original tree diameter is 3 (path from node 2 to node 4 or 5). Adding an edge creates a cycle, so the diameter cannot increase beyond original diameter. The maximum diameter remains 3.

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