Level Order Traversal of Binary Tree

Level Order Traversal ek Breadth-First Search (BFS) algorithmic traversal hai jisme tree ke nodes ko level-by-level (top to bottom) aur har level ke andar left to right visit kiya jata hai.

Algorithm using FIFO Queue

Depth-first traversals stack ya recursion se hote hain, lekin Level Order Traversal ke liye ek FIFO Queue data structure use kiya jata hai:

1. Ek empty queue create karein.
2. Root node ko queue me ENQUEUE karein.
3. Jab tak queue empty na ho, repeat karein:
   • Front node ko DEQUEUE karein aur print karein: curr = dequeue()
   • Agar curr->left exist karta hai, toh use queue me ENQUEUE karein.
   • Agar curr->right exist karta hai, toh use queue me ENQUEUE karein.

Tree:
Level 0:        [ 10 ]
               /      \
Level 1:    [ 20 ]   [ 30 ]
           /      \
Level 2: [ 40 ]  [ 50 ]

Queue Execution Trace:
1. Enqueue 10                  Queue: [ 10 ]
2. Dequeue 10, Enqueue 20, 30  Queue: [ 20, 30 ]         Output: 10
3. Dequeue 20, Enqueue 40, 50  Queue: [ 30, 40, 50 ]     Output: 10, 20
4. Dequeue 30                  Queue: [ 40, 50 ]         Output: 10, 20, 30
5. Dequeue 40                  Queue: [ 50 ]             Output: 10, 20, 30, 40
6. Dequeue 50                  Queue: [ ]                Output: 10, 20, 30, 40, 50

Complexity: Time Complexity O(n) (har node 1 bar queue me jata hai aur 1 bar nikalta hai). Space Complexity O(w) jahan w maximum width of tree hai (at most n/2 nodes in queue).

Agli post me hum cover karenge Binary Search Tree (BST): Concept and Search Operation.