Level Order Traversal of a Binary Tree

Level order or Depth order binary tree traversal is a technique used to visit all the nodes of a binary tree layer by layer. First the root node, which is at depth-0, is visited. Next all nodes at depth-1 (distance of 1 from root node) are visited. Next all the nodes at dept-2 are visited and so on. The animated examples discussed in the next section will make the definition more clear.

Animation of Level Order Binary Tree Traversal

Let’s consider the below binary tree and apply the Level order tree traversal technique:

First the root node A which is at depth 0 has to be visited.

Next all the nodes at depth 1 have to be visited (Nodes B and C).

Finally, all the nodes at depth 2 should be visited (Nodes D, E, F and G).

Iterative Implementation


from collections import deque

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def iterative_level_order_traversal(root):
    if root is None:
        return
    
    queue = deque()
    queue.append(root)

    while queue:
        node = queue.popleft()
        # Print the value or perform any operation
        print(node.value, end=" ")

        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

# Create a sample binary tree
def create_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)
    return root

# Iterative level-order traversal usage
if __name__ == "__main__":
    tree_root = create_binary_tree()
    print("Iterative Level-Order Traversal:")
    iterative_level_order_traversal(tree_root)