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 towns. The diameter is the longest route you can drive without repeating roads. We find it by looking at the longest two roads leaving each town and combining them.

      1
     / \
    2   3
   /     \
  4       5

Each number is a node. Arrows show connections. The diameter is the longest path between any two nodes.

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 (diameter).

Step 1: Start DFS from node 1 to calculate height of each subtree

Heights: 4 -> 0, 2 -> 1, 5 -> 0, 3 -> 1, 1 -> ?

Why: We need subtree heights to find longest paths through nodes

Step 2: Calculate height of node 2 as max height of children + 1 = 1

Heights: 4 -> 0, 2 -> 1, 5 -> 0, 3 -> 1, 1 -> ?

Why: Height helps find longest path down from node

Step 3: Calculate height of node 3 as max height of children + 1 = 1

Heights: 4 -> 0, 2 -> 1, 5 -> 0, 3 -> 1, 1 -> ?

Why: Same as node 2, height is needed for diameter calculation

Step 4: Calculate height of node 1 as max height of children + 1 = 2

Heights: 4 -> 0, 2 -> 1, 5 -> 0, 3 -> 1, 1 -> 2

Why: Root height is max height of its children plus one

Step 5: At each node, check sum of top two heights of children to update diameter

At node 1: top heights 1 (node 2) and 1 (node 3), diameter candidate = 1 + 1 = 2 edges (3 nodes path)

Why: Longest path may pass through this node combining two longest child paths

Step 6: Update diameter to max found: 4 edges (5 nodes path: 4 -> 2 -> 1 -> 3 -> 5)

Diameter = 4 edges (5 nodes path)

Why: This is the longest path in the tree

Result:

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

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class TreeDiameter {
    private static List<int>[] graph;
    private static int diameter = 0;

    static int DFS(int node, int parent) {
        int maxHeight1 = 0, maxHeight2 = 0;
        foreach (int child in graph[node]) {
            if (child == parent) continue;
            int height = DFS(child, node) + 1;
            if (height > maxHeight1) {
                maxHeight2 = maxHeight1;
                maxHeight1 = height;
            } else if (height > maxHeight2) {
                maxHeight2 = height;
            }
        }
        diameter = Math.Max(diameter, maxHeight1 + maxHeight2);
        return maxHeight1;
    }

    public static void Main() {
        int n = 5;
        graph = new List<int>[n + 1];
        for (int i = 0; i <= n; i++) graph[i] = new List<int>();

        // Build tree edges
        graph[1].Add(2); graph[2].Add(1);
        graph[1].Add(3); graph[3].Add(1);
        graph[2].Add(4); graph[4].Add(2);
        graph[3].Add(5); graph[5].Add(3);

        DFS(1, -1);
        Console.WriteLine($"Diameter length (edges): {diameter}");
    }
}

foreach (int child in graph[node]) { if (child == parent) continue; int height = DFS(child, node) + 1;

Traverse children skipping parent to avoid cycles, calculate height of each subtree

if (height > maxHeight1) { maxHeight2 = maxHeight1; maxHeight1 = height; } else if (height > maxHeight2) { maxHeight2 = height; }

Keep track of top two maximum heights among children

diameter = Math.Max(diameter, maxHeight1 + maxHeight2);

Update diameter with sum of two largest heights through this node

return maxHeight1;

Return the largest height to parent for further calculation

Output

Diameter length (edges): 4

Complexity Analysis

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

Space: O(n) for storing the tree and recursion stack

vs Alternative: Naive approach checking all pairs is O(n^2), DP on trees reduces it to O(n)

Edge Cases

Single node tree

Diameter is zero because no edges exist

DSA C#

foreach (int child in graph[node]) { if (child == parent) continue; ...

Linear chain tree (like a linked list)

Diameter equals number of edges in chain, code correctly sums heights

DSA C#

diameter = Math.Max(diameter, maxHeight1 + maxHeight2);

Tree with multiple branches

Code finds two longest child heights at each node to compute diameter

DSA C#

if (height > maxHeight1) { maxHeight2 = maxHeight1; maxHeight1 = height; } else if (height > maxHeight2) { maxHeight2 = height; }

When to Use This Pattern

When asked for longest path between any two nodes in a tree, use DP on trees to find diameter by combining longest child paths at each node.

Common Mistakes

Mistake: Not skipping the parent node during DFS causing infinite recursion
Fix: Add a check to skip the parent node in DFS traversal

Mistake: Only tracking one longest height instead of two, missing diameter through node
Fix: Track top two maximum heights among children to compute 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 does the diameter of a tree represent in the context of DP on Trees?

easy

A. The height of the tree from the root

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

C. The number of nodes in the tree

D. The total sum of all node values

Solution

1. Step 1: Understand the definition of tree diameter

   The diameter is the longest path between any two nodes in a tree, not necessarily passing through the root.

2. Step 2: Differentiate diameter from other tree properties

   Height is the longest path from root to leaf, number of nodes is size, and sum of values is unrelated to diameter.

3. Final Answer:

   The longest path between any two nodes in the tree -> Option B

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 passes through root

2. Which of the following C# code snippets correctly initializes an adjacency list for a tree with n nodes?

easy

A. var graph = new List<int>[n]; for(int i=0; i

B. var graph = new List<int>(n); for(int i=0; i

C. var graph = new List(); for(int i=0; i

D. var graph = new List<int>[n]; graph = new List<int>();

Solution

1. Step 1: Understand adjacency list initialization in C#

   For n nodes, create an array of List<int> with size n, then initialize each element with new List<int>().

2. Step 2: Analyze each option

   A: var graph = new List<int>[n]; for(int i=0; i(); for(int i=0; i

3. Final Answer:

   var graph = new List<int>[n]; for(int i=0; i -> Option A

4. Quick Check:

   Array of lists initialized correctly [OK]

Hint: Use array of lists and initialize each element [OK]

Common Mistakes:

• Not initializing each list element
• Using List<int> without specifying size
• Overwriting array with a single list

3. Consider the following C# code snippet to compute the diameter of a tree. What will be the output printed?

using System;
using System.Collections.Generic;

class Program {
    static List<int>[] graph;
    static int diameter = 0;

    static int DFS(int node, int parent) {
        int max1 = 0, max2 = 0;
        foreach (var child in graph[node]) {
            if (child == parent) continue;
            int dist = DFS(child, node) + 1;
            if (dist > max1) {
                max2 = max1;
                max1 = dist;
            } else if (dist > max2) {
                max2 = dist;
            }
        }
        diameter = Math.Max(diameter, max1 + max2);
        return max1;
    }

    static void Main() {
        int n = 5;
        graph = new List<int>[n];
        for (int i = 0; i < n; i++) graph[i] = new List<int>();
        graph[0].Add(1); graph[1].Add(0);
        graph[1].Add(2); graph[2].Add(1);
        graph[1].Add(3); graph[3].Add(1);
        graph[3].Add(4); graph[4].Add(3);

        DFS(0, -1);
        Console.WriteLine(diameter);
    }
}

medium

A. 2

B. 5

C. 3

D. 4

Solution

1. Step 1: Understand the tree structure and DFS traversal

   The tree edges are: 0-1, 1-2, 1-3, 3-4. The longest path is from node 2 to node 4 passing through 1 and 3, length 3 edges.

2. Step 2: Trace DFS and diameter calculation

   DFS calculates max distances from each node's children. Diameter updates to max sum of two longest child paths. The longest path length is 3.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Longest path length = 3 edges [OK]

Hint: Diameter = longest path edges between two nodes [OK]

Common Mistakes:

• Counting nodes instead of edges
• Misunderstanding DFS return values
• Ignoring parent check in DFS

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

static int DFS(int node, int parent) {
    int maxDist = 0;
    foreach (var child in graph[node]) {
        if (child == parent) continue;
        int dist = DFS(child, node) + 1;
        if (dist > maxDist) maxDist = dist;
    }
    diameter = Math.Max(diameter, maxDist);
    return maxDist;
}

medium

A. It does not check for parent node, causing infinite recursion

B. It updates diameter inside the loop incorrectly

C. It returns distance without adding 1 for edge

D. It only considers the longest single path, missing combined paths for diameter

Solution

1. Step 1: Analyze how diameter is updated

   The code tracks only the longest single path from children, ignoring the sum of two longest paths needed for diameter.

2. Step 2: Understand diameter definition

   Diameter is the longest path between any two nodes, which may be sum of two longest child paths through current node, not just one.

3. Final Answer:

   It only considers the longest single path, missing combined paths for diameter -> Option D

4. Quick Check:

   Diameter needs sum of two longest paths [OK]

Hint: Diameter = sum of two longest child paths, not just one [OK]

Common Mistakes:

• Ignoring second longest path
• Forgetting to skip parent node
• Updating diameter inside loop incorrectly

5. Given a weighted tree where edges have positive weights, how would you modify the DP approach to find the diameter of the tree?

hard

A. Replace increments by edge weights when calculating distances in DFS

B. Ignore weights and count edges as 1 each

C. Use BFS instead of DFS without changes

D. Sum all edge weights and divide by number of edges

Solution

1. Step 1: Understand difference between unweighted and weighted trees

   In weighted trees, edge lengths vary, so distance must accumulate actual weights, not just count edges.

2. Step 2: Modify DFS to add edge weights

   Instead of adding 1 for each edge, add the weight of the edge when calculating distances and updating diameter.

3. Step 3: Ignore incorrect options

   Ignoring weights loses accuracy, BFS alone doesn't solve weighted distances, summing all weights is unrelated to diameter.

4. Final Answer:

   Replace increments by edge weights when calculating distances in DFS -> Option A

5. Quick Check:

   Use edge weights in distance sums [OK]

Hint: Add edge weights instead of 1 in DFS distance calculation [OK]

Common Mistakes:

• Counting edges as 1 ignoring weights
• Using BFS without weight handling
• Summing all weights unrelated to diameter