C# Coding Test Course, Finding the Diameter of a Tree

Hello, everyone! Today, we will discuss a problem of finding the diameter of a tree using C#. This article will help you understand through problem definition, algorithm design, implementation, and testing process.

Problem Definition

The diameter of a tree refers to the length of the longest path between two nodes in the tree. The given tree is represented by the number of vertices n and n-1 edges.
Based on this, write a function to calculate the diameter of the tree.

Input

n : Number of vertices (2 ≤ n ≤ 10^5)
n-1 edges that make up the tree. Each edge is given in the form of u v w, where u and v are connected vertices, and w is the weight between the two vertices.

Output

An integer value representing the diameter of the tree.

Algorithm Design

The most common method to find the diameter of a tree is to use “two depth-first searches (DFS).”
Below is a summary of the simple procedure.

Run DFS from an arbitrary vertex to find the farthest vertex A.
Run DFS again from vertex A to find the farthest vertex B, and calculate the distance.

This method can efficiently determine the diameter of the tree. In the worst case, the time complexity is O(n).

C# Code Implementation

Below is the C# code based on the above algorithm:

using System;
using System.Collections.Generic;

class TreeDiameter
{
    static List>[] graph;
    static bool[] visited;
    static int maxDistance;
    static int furthestNode;

    public static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        graph = new List>[n + 1];

        for (int i = 1; i <= n; i++)
        {
            graph[i] = new List>();
        }

        for (int i = 0; i < n - 1; i++)
        {
            var edge = Console.ReadLine().Split();
            int u = int.Parse(edge[0]);
            int v = int.Parse(edge[1]);
            int w = int.Parse(edge[2]);
            graph[u].Add(new Tuple(v, w));
            graph[v].Add(new Tuple(u, w));
        }

        // Finding the farthest vertex using first DFS
        visited = new bool[n + 1];
        maxDistance = 0;
        DFS(1, 0);

        // Finding the diameter using second DFS
        visited = new bool[n + 1];
        maxDistance = 0;
        DFS(furthestNode, 0);
        
        // Output the result
        Console.WriteLine(maxDistance);
    }

    static void DFS(int node, int distance)
    {
        visited[node] = true;

        if (distance > maxDistance)
        {
            maxDistance = distance;
            furthestNode = node;
        }

        foreach (var neighbor in graph[node])
        {
            if (!visited[neighbor.Item1])
            {
                DFS(neighbor.Item1, distance + neighbor.Item2);
            }
        }
    }
}

Code Explanation

1. graph: An array to store the edges of the tree in an adjacency list format.
2. visited: An array to track visited vertices during DFS.
3. maxDistance: Stores the length of the longest path found so far.
4. furthestNode: Stores the ID of the farthest vertex.
5. Main(): Receives the tree structure input and calls DFS twice to calculate the diameter of the tree.
6. DFS(int node, int distance): Implements the depth-first search function to recursively explore each vertex while updating the distance.

Test Cases

Your code can be validated with the following test cases:

Test Input

Expected Output

Description

If we draw the tree from the above input, it looks like this:

The diameter of the tree is the path starting from node 2 to node 4, with a total length of 3 + 2 + 4 = 9.

Conclusion

Today, we solved the problem of finding the diameter of a tree using C#.
This algorithm is a frequently encountered type in tree problems, so I encourage you to practice sufficiently.
Try various test cases to deepen your understanding.
Thank you!