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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of diameter calculation on a simple tree

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

DSA C

#include <stdio.h>
#include <stdlib.h>

#define MAX 5

int adj[MAX][MAX] = {0};
int visited[MAX] = {0};
int max_diameter = 0;

int dfs(int node) {
    visited[node] = 1;
    int max1 = 0, max2 = 0;
    for (int i = 0; i < MAX; i++) {
        if (adj[node][i] && !visited[i]) {
            int dist = dfs(i) + 1;
            if (dist > max1) {
                max2 = max1;
                max1 = dist;
            } else if (dist > max2) {
                max2 = dist;
            }
        }
    }
    if (max1 + max2 > max_diameter) {
        max_diameter = max1 + max2;
    }
    return max1;
}

int main() {
    adj[0][1] = adj[1][0] = 1;
    adj[1][2] = adj[2][1] = 1;
    adj[1][3] = adj[3][1] = 1;
    adj[3][4] = adj[4][3] = 1;

    dfs(0);
    printf("%d\n", max_diameter);
    return 0;
}

A 4

B 3

C 5

D 2

💡 Hint

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

The longest path (diameter) in this tree is from node 2 to node 4 passing through nodes 1 and 3, which has length 3 edges.

🧠 Conceptual

intermediate

Understanding the diameter calculation logic

In the DP approach to find the diameter of a tree, what does the sum of the two largest depths from a node represent?

A The height of the tree

B The total number of nodes in the tree

C The longest path passing through that node

D The number of leaf nodes

💡 Hint

Think about how the diameter can pass through a node connecting two longest branches.

The diameter is the longest path between any two nodes. At each node, the sum of the two largest depths of its children represents the longest path passing through that node.

❓ Predict Output

advanced

Output of diameter calculation with weighted edges

What is the output of the following C code that calculates the diameter of a weighted tree using DP on trees?

DSA C

#include <stdio.h>
#include <stdlib.h>

#define MAX 4

int adj[MAX][MAX] = {0};
int visited[MAX] = {0};
int max_diameter = 0;

int dfs(int node) {
    visited[node] = 1;
    int max1 = 0, max2 = 0;
    for (int i = 0; i < MAX; i++) {
        if (adj[node][i] > 0 && !visited[i]) {
            int dist = dfs(i) + adj[node][i];
            if (dist > max1) {
                max2 = max1;
                max1 = dist;
            } else if (dist > max2) {
                max2 = dist;
            }
        }
    }
    if (max1 + max2 > max_diameter) {
        max_diameter = max1 + max2;
    }
    return max1;
}

int main() {
    adj[0][1] = adj[1][0] = 3;
    adj[1][2] = adj[2][1] = 4;
    adj[1][3] = adj[3][1] = 2;

    dfs(0);
    printf("%d\n", max_diameter);
    return 0;
}

A 9

B 6

C 5

D 7

💡 Hint

Sum the two longest weighted paths from the root node.

The longest path is from node 2 to node 0 passing through node 1 with weights 4 + 3 = 7.

🔧 Debug

advanced

Identify the bug in diameter calculation code

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

DSA C

#include <stdio.h>
#include <stdlib.h>

#define MAX 3

int adj[MAX][MAX] = {0};
int visited[MAX] = {0};
int max_diameter = 0;

int dfs(int node) {
    visited[node] = 1;
    int max1 = 0, max2 = 0;
    for (int i = 0; i < MAX; i++) {
        if (adj[node][i] && !visited[i]) {
            int dist = dfs(i) + 1;
            if (dist > max1) {
                max2 = max1;
                max1 = dist;
            } else if (dist > max2) {
                max2 = dist;
            }
        }
    }
    if (max1 + max2 > max_diameter) {
        max_diameter = max1 + max2;
    }
    return max1;
}

int main() {
    adj[0][1] = 1;
    adj[1][0] = 1;
    adj[1][2] = 1;
    // Missing adj[2][1] = 1;

    dfs(0);
    printf("%d\n", max_diameter);
    return 0;
}

A The diameter will be underestimated due to missing edge

B The diameter will be overestimated due to double counting

C Compilation error due to missing semicolon

D Segmentation fault due to invalid memory access

💡 Hint

Check if the tree edges are correctly bidirectional.

The missing adj[2][1] = 1 means the edge from node 2 to 1 is missing, so DFS won't visit node 2 properly, underestimating the diameter.

🧠 Conceptual

expert

Why DP on trees is efficient for diameter calculation

Why is the DP approach on trees preferred over brute force for finding the diameter of a tree?

A It avoids repeated calculations by storing intermediate results, reducing time complexity to O(n)

B It uses more memory but runs slower than brute force

C It only works for binary trees, not general trees

D It requires sorting all nodes which increases complexity

💡 Hint

Think about how DP avoids repeated work in recursive tree traversal.

DP on trees stores the longest paths from children to avoid recalculating them, making the diameter calculation efficient in linear time.