DIAMTREE - Editorial

Problem Link - Find Tree Diameter

Problem Statement

You’re given a tree with N vertices numbered from 1 to N. A tree is defined as a connected, undirected graph with N vertices and N-1 edges. The distance between two vertices in a tree is equal to the number of edges on the unique simple path between them.

The diameter of a tree is the maximum distance between two nodes. Your task is to determine the diameter of the tree.

Approach

The code uses a “two-pass BFS” to find the tree’s diameter. First, we run BFS from an arbitrary node (node 1) to find the farthest node, called a leaf. Then, we run BFS again from this leaf to find the farthest node from it. The distance between these two nodes is the tree’s diameter. This method is efficient as BFS runs twice, each taking O(N) time

Time Complexity

The time complexity is O(N), as we perform two BFS operations.

Space Complexity

The space complexity is O(N), due to the adjacency list and queue used for BFS.