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

1. Problem Definition

This is the problem of finding the diameter of a given tree. The diameter of a tree refers to the length of the longest path between any two nodes. A tree is a graph composed of nodes and edges, characterized as a connected graph without cycles. To solve this problem, we can use either the DFS (Depth First Search) or BFS (Breadth First Search) algorithm.

2. Problem Input

The first line contains the number of nodes N. From the next line onwards, N-1 lines contain the edges, with each edge represented by two integers a and b. This indicates that there is an edge between node a and node b.

Input Example

    5
    1 2
    1 3
    2 4
    2 5

3. Problem Output

The program outputs the diameter of the tree.

Output Example

    3

4. Algorithm Explanation

The algorithm for finding the diameter of a tree proceeds as follows:

  1. Store the tree in the form of an adjacency list.
  2. Use the first DFS to find the farthest node.
  3. Use a second DFS to find the farthest node from the one identified in the first DFS.
  4. The result of the second DFS is the diameter of the tree.

5. C++ Code Implementation

The C++ code to calculate the diameter of the tree is as follows:


#include 
#include 
#include 

using namespace std;

vector > tree;
vector visited;

int furthestNode(int node) {
    visited[node] = true;

    int maxDistance = 0;
    int farthestNode = node;

    for (int neighbor : tree[node]) {
        if (!visited[neighbor]) {
            int distance = furthestNode(neighbor) + 1;
            if (distance > maxDistance) {
                maxDistance = distance;
                farthestNode = neighbor;
            }
        }
    }

    return farthestNode;
}

int main() {
    int N;
    cin >> N;

    tree.resize(N + 1);
    visited.resize(N + 1, false);

    for (int i = 0; i < N - 1; i++) {
        int a, b;
        cin >> a >> b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }

    int farthestFromStart = furthestNode(1);
    
    fill(visited.begin(), visited.end(), false);
    
    int diameterEnd = furthestNode(farthestFromStart);
    
    cout << diameterEnd << endl;

    return 0;
}

6. Code Explanation

The code is structured as follows:

  1. Include libraries and declare global variables.
  2. Perform DFS through the furthestNode function to return the farthest node.
  3. In the main function, read input and construct the tree.
  4. Use the first DFS to find the farthest node from the starting node.
  5. Use the second DFS to find the farthest node from the node found in the first DFS, which will be the end of the diameter.
  6. Output the length of the diameter.

7. Time Complexity Analysis

The time complexity of this algorithm is O(N). It executes DFS for each node while visiting N nodes, thus it is proportional to the size of the tree.

8. Conclusion

In this lesson, we learned how to solve the problem of finding the diameter of a tree. It is important to understand the process of exploring the tree’s structure and deriving a solution using DFS. By practicing various graph problems, you can enhance your algorithm skills.

9. References