Top 10 Programming Languages to Learn in 2019

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

Page Contents

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

### Creating and Modifying PDF Files in Python: A Comprehensive Guide with Code Examples

This site uses Akismet to reduce spam. Learn how your comment data is processed.