Prerequisites :- DFS or BFS
Problem :- Given an undirected connected tree with N nodes, numbered from 1 to N, and rooted at node 1, find the height of the tree.
Solution Approach:
The problem can be efficiently solved using Depth First Search (DFS) on the tree. Please note that BFS can also be used.
Kindly note that, the height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
The basic idea is to perform a DFS traversal starting from the root node and keep track of the depth (distance from the root) of each node. The maximum depth encountered during the traversal will be the height of the tree.
- Start a DFS traversal from the root node (node 1) with an initial depth of 0.
- For each neighbor v of the current node, if v is not the parent node (to avoid going back to the parent), recursively call DFS on v with depth increased by 1.
- Update the maximum depth encountered during the traversal.
Time Complexity:
The DFS traversal visits each node and edge once, leading to a time complexity of O(N + E), where N is the number of nodes and E is the number of edges (= N - 1, in case of tree). Hence the overall time complexity is O(N).
Space Complexity:
The space complexity is O(N) for storing the adjacency list and recursion stack during DFS.