DP on Trees Diameter of Tree in DSA C

Mental Model

The diameter of a tree is the longest path between any two nodes. We find it by checking the longest paths through each node using dynamic programming.

Analogy: Imagine a network of roads connecting cities. The diameter is the longest route you can take between two cities without repeating roads. We find it by looking at the longest roads from each city and combining them.

      1
     / \
    2   3
   /     \
  4       5

Each number is a city (node), lines are roads (edges).

Dry Run Walkthrough

Input: Tree edges: 1-2, 1-3, 2-4, 3-5

Goal: Find the longest path between any two nodes in the tree

Step 1: Start DFS from node 1, calculate longest path down from node 4

4 -> null (leaf node, longest path down = 0)

Why: Leaf nodes have no children, so longest path down is zero

Step 2: Calculate longest path down from node 2 using child 4

2 -> 4 -> null (longest path down from 2 is 1)

Why: Longest path down from 2 is 1 edge to 4

Step 3: Calculate longest path down from node 5 (leaf)

5 -> null (longest path down = 0)

Why: Leaf node 5 has no children

Step 4: Calculate longest path down from node 3 using child 5

3 -> 5 -> null (longest path down from 3 is 1)

Why: Longest path down from 3 is 1 edge to 5

Step 5: Calculate diameter passing through node 1 using top two longest child paths (2 and 3)

Diameter candidates: path through 1 = 1 (2->4) + 1 (3->5) = 2 edges

Why: Diameter can pass through node 1 combining longest paths from two children

Step 6: Compare diameter candidates and update global diameter

Diameter = 4 edges (path 4->2->1->3->5)

Why: Longest path found is between nodes 4 and 5 through 1

Result:

Diameter path: 4 -> 2 -> 1 -> 3 -> 5 -> null, Diameter length = 4 edges

Annotated Code

DSA C

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

#define MAX 100

// Structure for adjacency list node
typedef struct Node {
    int val;
    struct Node* next;
} Node;

Node* graph[MAX];
int diameter = 0;

// Add edge to undirected graph
void addEdge(int u, int v) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->val = v;
    node->next = graph[u];
    graph[u] = node;

    node = (Node*)malloc(sizeof(Node));
    node->val = u;
    node->next = graph[v];
    graph[v] = node;
}

// DFS to find longest path down from node and update diameter
int dfs(int u, int parent) {
    int max1 = 0, max2 = 0; // top two longest child paths
    for (Node* curr = graph[u]; curr != NULL; curr = curr->next) {
        int v = curr->val;
        if (v == parent) continue; // avoid going back
        int length = dfs(v, u) + 1; // path length from child
        if (length > max1) {
            max2 = max1;
            max1 = length;
        } else if (length > max2) {
            max2 = length;
        }
    }
    if (max1 + max2 > diameter) {
        diameter = max1 + max2; // update global diameter
    }
    return max1; // return longest path down
}

int main() {
    // Build tree from example
    addEdge(1, 2);
    addEdge(1, 3);
    addEdge(2, 4);
    addEdge(3, 5);

    dfs(1, -1);
    printf("Diameter length = %d\n", diameter);
    return 0;
}

for (Node* curr = graph[u]; curr != NULL; curr = curr->next) {

Traverse all children of current node u

if (v == parent) continue;

Skip the parent node to avoid revisiting

int length = dfs(v, u) + 1;

Recursively find longest path down from child v and add edge

if (length > max1) { max2 = max1; max1 = length; } else if (length > max2) { max2 = length; }

Keep track of top two longest child paths

if (max1 + max2 > diameter) { diameter = max1 + max2; }

Update global diameter if current node's paths form longer path

return max1;

Return longest path down from current node

Output

Diameter length = 4

Complexity Analysis

Time: O(n) because we visit each node once during DFS

Space: O(n) for storing adjacency list and recursion stack

vs Alternative: Naive approach checks all pairs of nodes for longest path, which is O(n^2), so DP on trees is much faster

Edge Cases

Single node tree

Diameter is zero because no edges exist

DSA C

if (v == parent) continue;

Linear tree (chain)

Diameter equals number of edges in the chain

DSA C

if (max1 + max2 > diameter) { diameter = max1 + max2; }

Tree with multiple branches

Diameter is longest path through some node combining two longest child paths

DSA C

if (max1 + max2 > diameter) { diameter = max1 + max2; }

When to Use This Pattern

When asked to find the longest path between any two nodes in a tree, use DP on trees by combining longest paths from children to find diameter efficiently.

Common Mistakes

Mistake: Not skipping the parent node in DFS causing infinite loops
Fix: Add check to skip parent node: if (v == parent) continue;

Mistake: Only tracking one longest child path, missing diameter through node
Fix: Track top two longest child paths to combine for diameter

Summary

Finds the longest path between any two nodes in a tree using DFS and dynamic programming.

Use when you need the maximum distance between nodes in a tree structure.

The diameter passes through a node combining its two longest child paths.

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