Prerequisites:- Trees or Graph
Problem :- Given a tree with N vertices and N−1 edges, rooted at node number 1. Output the nodes while traversing the tree in DFS order.
Solution Approach:- In a tree data structure, the absence of cycles is a fundamental property. This concept is leveraged in the approach described here. During the Depth-First Search (DFS) function call, we maintain awareness of both the parent node and the current node. The objective is to navigate down the depth until all children of the current node are visited and then backtrack to its parent. The crucial principle is to avoid reaching the parent node prematurely, especially when some children of the current node are yet to be explored.
Tree traversal shares similarities with graph traversal, as it is a form of graph traversal. Depth-First Search traversal on a graph closely resembles its counterpart on a tree. The primary distinction lies in the fact that a tree is a specialized type of connected graph without cycles.
Conversely, in DFS traversal on a general graph, additional memory is required to keep track of visited nodes to prevent revisiting them. Unlike trees, graphs can have cycles, and they may not necessarily be connected. Therefore, the tracking of visited nodes becomes essential in graph traversal to handle these variations.
Time Complexity: O(N+E) - Each node and each edge are visited once during BFS traversal, where N is the number of vertices, and E is the number of edges. E = N - 1 in case of trees. Hence, the ultimate time complexity is O(N).
Space Complexity: O(1) - as no extra space is needed.