Prerequisites :- DFS
Problem :- Given an undirected connected tree with N nodes, numbered from 1 to N, and rooted at node 1, find the length of the diameter of the tree (Note: Diameter of a tree is the longest path between any two nodes. There can be more than one diameter of a tree with the same length).
Solution Approach:
First of all, what’s the diameter of a tree?
The diameter of a tree is the number of nodes on the longest path between two leaves in the tree.
The problem can be solved using a two-step Depth-First Search (DFS) approach
First DFS for Farthest Node:
- Perform the first DFS to find the farthest node from the starting node (node 1).
- This is done by updating the distance array during the DFS traversal.
Second DFS for Diameter:
- Use the farthest node found in the first DFS as the starting node for the second DFS.
- Traverse the tree from the farthest node and update the distance array again.
- The maximum distance encountered during this traversal is the diameter of the tree.
Finally, print the diameter of the tree.
Time Complexity: O(N + E) = O(N), where N is the number of nodes and E is the no. of edges in the tree. The two DFS traversals visit each node and edge once.
Space Complexity: O(N), as the algorithm utilizes an array to store distances for each node.