.png)
DSA Series Chapter 16 – LEVEL ORDER TRAVERSAL(BINARY TREE BFS)(Python Version)
1. Level Order Traversal – Quick Recall
Definition:
Level Order Traversal visits nodes level by level from left to right, starting from the root.
Category:
Breadth First Search (BFS)
2. Binary Tree Used (Same as C Version)
1
/ \
2 3
/ \
4 5
Expected Output
1 2 3 4 5
3. Node Structure in Python
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
4. Algorithm (Plain English)
If the tree is empty, stop
Create an empty queue
Insert root node into the queue
While queue is not empty:
Remove front node
Visit (print/process) the node
Insert left child (if exists)
Insert right child (if exists)
5. Python Program – Level Order Traversal (Using Queue)
Using collections.deque (Recommended)
from collections import deque
def level_order(root):
if root is None:
return
queue = deque()
queue.append(root)
while queue:
current = queue.popleft()
print(current.data, end=" ")
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
6. Complete Executable Python Program
from collections import deque
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def level_order(root):
if root is None:
return
queue = deque()
queue.append(root)
while queue:
current = queue.popleft()
print(current.data, end=" ")
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
# Tree creation
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
print("Level Order Traversal:")
level_order(root)
Output
Level Order Traversal:
1 2 3 4 5
7. Dry Run (Queue Simulation)
Queue: [1]
Dequeue 1 → print 1 → enqueue 2, 3
Queue: [2, 3]
Dequeue 2 → print 2 → enqueue 4, 5
Queue: [3, 4, 5]
Dequeue 3 → print 3
Queue: [4, 5]
Dequeue 4 → print 4
Queue: [5]
Dequeue 5 → print 5
Queue empty → stop
8. Time and Space Complexity
Time Complexity
O(n) — each node visited once
Space Complexity
O(n) — queue may store up to all nodes of a level
9. Important Applications
Printing tree level by level
Finding height/levels of a tree
BFS-based tree problems
10. Common Student Mistakes
Using list instead of queue without proper dequeue handling
Forgetting to enqueue child nodes
Confusing BFS with DFS traversals
11. Practice Questions
Write level order traversal for a left-skewed tree.
Predict output for a tree with only right children.
Modify level order traversal to print each level on a new line.
Implement level order traversal without using
deque.
ALSO CHECK
ALSO CHECK
Comments
Post a Comment