DP on Trees Diameter of Tree in DSA C# - Execution Trace

Concept Flow - DP on Trees Diameter of Tree

Start at any node

↓

DFS to find farthest node A

↓

DFS from node A to find farthest node B

↓

Diameter = distance between A and B

↓

Use DP to store max depths at each node

↓

Calculate max path through each node

↓

Update global max diameter

↓

Return max diameter

Find diameter by two DFS traversals and use DP to store max depths for efficient calculation.

Execution Sample

DSA C#

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

DFS calculates max depths of subtrees and updates diameter as sum of top two depths at each node.

Execution Table

Step	Operation	Current Node	Max Depths (max1, max2)	Diameter Update	Visual State (Tree with depths)
1	Start DFS at node 1	1	(0,0)	Diameter=0	1(0)
2	Visit child node 2	2	(0,0)	Diameter=0	1(0) -> 2(0)
3	Visit child node 4	4	(0,0)	Diameter=0	1(0) -> 2(0) -> 4(0)
4	Return from node 4	4	(0,0)	Diameter=0	4 depth=0
5	Update node 2 depths	2	(1,0)	Diameter=0	2 depth=1
6	Visit child node 5	5	(0,0)	Diameter=0	2(1) -> 5(0)
7	Return from node 5	5	(0,0)	Diameter=0	5 depth=0
8	Update node 2 depths	2	(1,1)	Diameter=2	2 depth=1, Diameter=2
9	Return from node 2	2	(1,1)	Diameter=2	2 depth=1
10	Visit child node 3	3	(0,0)	Diameter=2	1(0) -> 3(0)
11	Visit child node 6	6	(0,0)	Diameter=2	3(0) -> 6(0)
12	Return from node 6	6	(0,0)	Diameter=2	6 depth=0
13	Update node 3 depths	3	(1,0)	Diameter=2	3 depth=1
14	Visit child node 7	7	(0,0)	Diameter=2	3(1) -> 7(0)
15	Return from node 7	7	(0,0)	Diameter=2	7 depth=0
16	Update node 3 depths	3	(1,1)	Diameter=2	3 depth=1
17	Return from node 3	3	(1,1)	Diameter=2	3 depth=1
18	Update node 1 depths	1	(2,2)	Diameter=4	1 depth=2, Diameter=4
19	DFS complete	1	(2,2)	Diameter=4	Final Diameter=4

💡 All nodes visited, diameter updated to max sum of two max depths at any node.

Variable Tracker

Variable	Start	After Step 5	After Step 8	After Step 13	After Step 18	Final
Diameter	0	0	2	2	4	4
max1 (node 1)	0	0	0	0	2	2
max2 (node 1)	0	0	0	0	2	2
max1 (node 2)	0	1	1	1	1	1
max2 (node 2)	0	0	1	1	1	1
max1 (node 3)	0	0	0	1	1	1
max2 (node 3)	0	0	0	0	1	1

Key Moments - 3 Insights

Why do we keep track of two max depths (max1 and max2) at each node?

Because the diameter can pass through the current node combining two longest paths from its children, so we need the top two depths to calculate max path through that node (see steps 8 and 18).

Why do we add 1 to the child's depth when returning from DFS?

Adding 1 accounts for the edge between the current node and its child, so depth represents number of edges from current node down to leaf (see steps 5 and 13).

Why do we update the global diameter inside DFS instead of after?

Updating diameter during DFS ensures we consider all nodes as potential path centers immediately, avoiding extra traversal (see steps 8, 18).

Visual Quiz - 3 Questions

Look at the execution table at step 8, what is the diameter value?

A 2

B 1

C 0

D 3

💡 Hint

Check the 'Diameter Update' column at step 8 in the execution_table.

At which step does the diameter first update to 4?

A Step 13

B Step 18

C Step 8

D Step 19

💡 Hint

Look for the first 'Diameter=4' in the 'Diameter Update' column.

If we remove node 7, how would max2 at node 3 change after step 16?

A It would become 2

B It would remain 1

C It would become 0

D It would become -1

💡 Hint

Without node 7, node 3 has only one child with depth 1, so second max depth is 0 (see variable_tracker).

Concept Snapshot

DP on Trees Diameter:
- Use DFS to find max depths of subtrees
- Track two largest depths (max1, max2) at each node
- Diameter = max sum of max1 + max2 over all nodes
- Update diameter during DFS
- Return global diameter after traversal

Full Transcript

To find the diameter of a tree using DP, we perform a DFS starting from any node. At each node, we calculate the two longest depths from its children. We keep track of these as max1 and max2. The diameter can be the sum of these two depths at any node, so we update a global diameter variable during DFS. After visiting all nodes, the global diameter holds the longest path length in the tree. This method efficiently computes diameter in one traversal by storing subtree depths and updating diameter on the fly.

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