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.