Prerequisites :- DFS
Problem :- Given an undirected connected tree with N nodes, numbered from 1 to N, rooted at node 1, and a positive integer K. Print/Find all the nodes at the level K from root node in sorted order.
Solution Approach:
We can use Depth-First Search (DFS) to traverse the tree and find the nodes at the specified level. The DFS algorithm is designed to handle the traversal, taking into account the current node, its parent, the target level, and the current level.
If the current level matches the target level, the current node is added to the list of nodes at the Kth level.
For each neighbor of the current node, the DFS function is called recursively, excluding the parent node.
After the traversal, the nodes found at the Kth level can be sorted and then printed.
Time Complexity:
The DFS traversal has a time complexity of O(N + E) = O(N), where N is the number of nodes, E is no of edges, which is equal to N - 1 in case of trees . Sorting the nodes at the Kth level adds an additional O(N log N) time, because in the worst case there could be O(N) nodes at Kth level. Consequently, the overall time complexity is O(N log N).
Space Complexity:
The space complexity is O(N) due to the adjacency list, the nodes at the Kth level, and the recursive call stack during DFS. The depth of the recursive call stack is at most the height of the tree, which is O(N) in the worst case for an unbalanced tree.