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.