Level Order Tree Traversal in Python

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.

Algorithm

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.

Python Code

# 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)

Output

The output of the above code is:

1 2 3 4 5 6 7 

Explanation

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.