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 BFS order.
Solution Approach :-
The problem involves performing a Breadth-First Search (BFS) traversal of a tree rooted at node 1. Here’s the solution approach:
- Initialize Data Structures:
- Create a queue to store nodes during BFS traversal.
- Create a boolean array to keep track of visited nodes to avoid revisiting.
- BFS Traversal:
- Start with the root node (node 1) and enqueue it.
- While the queue is not empty:
- Dequeue a node, output its value, and mark it as visited.
- Enqueue all unvisited children of the dequeued node.
- Continue this process until the queue is empty.
- Output:
- The output sequence represents the BFS order of nodes in the tree.
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. So, ultimately, the time complexity is O(N)
Space Complexity: O(N) - The space required for the queue and the boolean array for visited nodes.