DP on Trees Diameter of Tree in DSA C - Build from Scratch

DP on Trees: Diameter of Tree

📖 Scenario: You are working on a network of computers connected by cables. The network forms a tree structure where each computer is a node, and cables are edges. You want to find the longest path between any two computers in this network. This longest path is called the diameter of the tree.

🎯 Goal: Build a program in C that uses dynamic programming on trees to find the diameter of a given tree. You will represent the tree using adjacency lists, compute the diameter using a depth-first search (DFS) with DP, and print the diameter length.

📋 What You'll Learn

Create an adjacency list to represent the tree with 5 nodes and given edges

Create a global variable to store the maximum diameter found

Write a DFS function that returns the longest path from a node down to its descendants and updates the diameter

Print the diameter of the tree after DFS traversal

💡 Why This Matters

🌍 Real World

Finding the diameter of a tree is useful in network design, biology (evolution trees), and communication systems to understand the longest delay or distance between nodes.

💼 Career

Understanding tree diameters and dynamic programming on trees is important for software engineers working on graph algorithms, network optimization, and competitive programming.

1

Create the tree adjacency list

Create an adjacency list called adj for a tree with 5 nodes (numbered 0 to 4). Add edges: 0-1, 0-2, 1-3, 1-4. Use an array of vectors or arrays to store neighbors.

DSA C

# Define adjacency list for 5 nodes
// Your code here

Hint

Use two arrays: adj to store neighbors and adj_size to track number of neighbors for each node. Add edges in both directions.

2

Create a global variable for diameter

Add a global integer variable called diameter and initialize it to 0. This will store the maximum diameter found during DFS.

DSA C

#include 
#include 

#define N 5

int adj[N][N];
int adj_size[N];

int diameter = 0; // Your code here

int main() {
    for (int i = 0; i < N; i++) {
        adj_size[i] = 0;
    }
    // Add edge 0-1
    adj[0][adj_size[0]++] = 1;
    adj[1][adj_size[1]++] = 0;
    // Add edge 0-2
    adj[0][adj_size[0]++] = 2;
    adj[2][adj_size[2]++] = 0;
    // Add edge 1-3
    adj[1][adj_size[1]++] = 3;
    adj[3][adj_size[3]++] = 1;
    // Add edge 1-4
    adj[1][adj_size[1]++] = 4;
    adj[4][adj_size[4]++] = 1;
    return 0;
}

Hint

Declare diameter outside main so it is global and accessible in other functions.

3

Write DFS function to compute diameter

Write a function int dfs(int node, int parent) that returns the longest path from node down to its descendants. Inside, find the top two longest child paths, update the global diameter with their sum if larger, and return the longest child path plus one.

DSA C

    int max1 = 0, max2 = 0;
    for (int i = 0; i  max1) {
            max2 = max1;
            max1 = length;
        } else if (length > max2) {
            max2 = length;
        }
    if (max1 + max2 > diameter) {
        diameter = max1 + max2;
    return max1 + 1;
    dfs(0, -1);

Hint

Use two variables max1 and max2 to track the longest and second longest child paths. Update diameter with their sum. Return max1 + 1 for the current node's longest path.

4

Print the diameter of the tree

Add a printf statement in main to print the value of diameter after calling dfs(0, -1). The output should be the diameter number.

DSA C

Hint

Call printf("%d\n", diameter); after DFS to print the diameter.

Practice

1. What is the diameter of a tree in the context of dynamic programming on trees?

easy

A. The height of the tree from the root

B. The number of nodes in the tree

C. The sum of all edge weights in the tree

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

Solution

1. Step 1: Understand the definition of tree diameter

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

2. Step 2: Differentiate from other tree properties

   Height is from root to leaf, sum of edges is total weight, and node count is size, none represent longest path.

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 is number of nodes
• Assuming diameter is sum of all edges

2. Which of the following is the correct way to declare an adjacency list for a tree with n nodes in C?

easy

A. int adj[n][n];

B. int* adj[n];

C. int adj[n];

D. int adjList[n][2];

Solution

1. Step 1: Understand adjacency list structure

   An adjacency list uses an array of pointers to lists (or arrays) of neighbors, so int* adj[n]; is correct.

2. Step 2: Differentiate from other declarations

   int adj[n][n]; is adjacency matrix, int adj[n]; is a simple array, int adjList[n][2]; is edge list, not adjacency list.

3. Final Answer:

   int* adj[n]; -> Option B

4. Quick Check:

   Adjacency list uses array of pointers [OK]

Hint: Adjacency list uses array of pointers to neighbors [OK]

Common Mistakes:

• Using 2D array as adjacency list
• Using simple array for adjacency
• Confusing edge list with adjacency list

3. Consider the following C code snippet to find the diameter of a tree. What will be the output if the tree has edges: 1-2, 2-3, 2-4?

int diameter = 0;
int dfs(int node, int parent, vector<int> adj[]) {
    int max1 = 0, max2 = 0;
    for (int child : adj[node]) {
        if (child == parent) continue;
        int height = dfs(child, node, adj) + 1;
        if (height > max1) {
            max2 = max1;
            max1 = height;
        } else if (height > max2) {
            max2 = height;
        }
    }
    diameter = max(diameter, max1 + max2);
    return max1;
}
// Call dfs(1, -1, adj) and then print diameter;

medium

A. 2

B. 3

C. 1

D. 4

Solution

1. Step 1: Trace DFS from node 1

   From node 1, child is 2. DFS(2) explores children 3 and 4. Heights from 3 and 4 are 1 each.

2. Step 2: Calculate diameter updates

   At node 2, max1=1, max2=1, diameter updated to 2. At node 1, max1=2, max2=0, diameter remains 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Longest path length = 2 edges [OK]

Hint: Diameter = sum of two longest child heights [OK]

Common Mistakes:

• Counting nodes instead of edges
• Not updating diameter correctly
• Ignoring parent to avoid cycles

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

int diameter = 0;
int dfs(int node, int parent, vector<int> adj[]) {
    int max1 = 0, max2 = 0;
    for (int child : adj[node]) {
        int height = dfs(child, node, adj) + 1;
        if (height > max1) {
            max2 = max1;
            max1 = height;
        } else if (height > max2) {
            max2 = height;
        }
    }
    diameter = max(diameter, max1 + max2);
    return max1;
}
// Called with dfs(1, -1, adj);

medium

A. Incorrect initialization of diameter variable

B. Returning max2 instead of max1 from DFS

C. Missing check to skip parent node in DFS

D. Not adding 1 to height in DFS call

Solution

1. Step 1: Identify missing parent check in DFS loop

   The code does not skip the parent node, causing infinite recursion or wrong heights.

2. Step 2: Explain impact of missing check

   Without skipping parent, DFS revisits parent, causing incorrect diameter calculation or stack overflow.

3. Final Answer:

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

4. Quick Check:

   Skip parent to avoid cycles [OK]

Hint: Always skip parent node in DFS to prevent cycles [OK]

Common Mistakes:

• Forgetting to skip parent node
• Returning wrong height value
• Incorrect diameter initialization

5. Given a weighted tree with edges: (1-2, 3), (2-3, 4), (2-4, 2), how would you modify the diameter calculation to find the longest weighted path? Choose the correct approach.

hard

A. Add edge weights to height calculations and update diameter with weighted sums

B. Ignore weights and use number of edges as diameter

C. Multiply edge weights instead of adding

D. Use BFS twice without considering weights

Solution

1. Step 1: Incorporate edge weights in DFS height calculation

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

2. Step 2: Update diameter with sum of two largest weighted heights

   Keep track of two largest weighted heights from children and update diameter with their sum.

3. Final Answer:

   Add edge weights to height calculations and update diameter with weighted sums -> Option A

4. Quick Check:

   Weighted diameter sums edge weights [OK]

Hint: Add weights to heights, sum two largest for diameter [OK]

Common Mistakes:

• Ignoring weights in diameter calculation
• Multiplying weights instead of adding
• Using unweighted BFS for weighted tree