Level order tree traversal is a technique to visit all the nodes of a binary tree in a way that nodes at the same level are visited before nodes at a lower level. It is also known as breadth-first search or BFS.
The algorithm for level order tree traversal can be summarized as follows:
- Create an empty queue and enqueue the root node of the tree.
- While the queue is not empty, do the following steps:
- Dequeue a node from the queue and print its value.
- If the node has a left child, enqueue it to the queue.
- If the node has a right child, enqueue it to the queue.
# Define a class for the nodes of the binary tree class Node: def __init__(self, data): self.data = data self.left = None self.right = None # Define a function to perform level order traversal def level_order_traversal(root): # Create an empty queue queue =  # Enqueue the root node queue.append(root) # Loop until the queue is empty while queue: # Dequeue a node from the queue node = queue.pop(0) # Print its value print(node.data, end=" ") # Enqueue its left child if exists if node.left: queue.append(node.left) # Enqueue its right child if exists if node.right: queue.append(node.right) # Create a sample binary tree root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.left = Node(6) root.right.right = Node(7) # Call the function to perform level order traversal level_order_traversal(root)
The output of the above code is:
1 2 3 4 5 6 7
The above code creates a binary tree with the following structure:
1 / \ 2 3 / \ / \ 4 5 6 7
The level order traversal of this tree is:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
The code uses a queue to store the nodes that need to be visited next. It starts with enqueuing the root node (1) and then dequeues it and prints its value. Then it enqueues its left child (2) and right child (3) to the queue. The queue now contains [2, 3].
The next iteration dequeues the node (2) and prints its value. Then it enqueues its left child (4) and right child (5) to the queue. The queue now contains [3, 4, 5].
The next iteration dequeues the node (3) and prints its value. Then it enqueues its left child (6) and right child (7) to the queue. The queue now contains [4, 5, 6, 7].
The next iterations dequeue and print the remaining nodes in the queue until it becomes empty.