Level Order Traversal in Binary Trees

Tree traversal is the process of visiting every node in a tree exactly once in a systematic way. There are several types of tree traversals:

• Preorder Traversal
• Inorder Traversal
• Postorder Traversal
• Level Order Traversal

In this blog, we'll focus on level order traversal, its concept, and its implementation using both recursive and iterative approaches.

Understanding Level Order Traversal

Level order traversal visits nodes level by level, starting from the root. It processes nodes from top to bottom and left to right on each level. This traversal is typically implemented using a queue.

For example, consider the following binary tree:

                3
               / \
              4   5
             / \   \
            6   7   8
        

In level order traversal, the nodes will be visited in the following order: 3, 4, 5, 6, 7, 8.

Recursive Approach

The recursive approach for level order traversal typically involves using a helper function to process each level of the tree one by one. Although not as commonly used as the iterative approach, it's still an interesting method to explore.

from collections import deque

# Recursive Level Order Traversal Helper Function
def level_order_recursive(root):
    def helper(node, level, result):
        if not node:
            return
        if len(result) == level:
            result.append([])
        result[level].append(node.value)
        helper(node.left, level + 1, result)
        helper(node.right, level + 1, result)

    result = []
    helper(root, 0, result)
    return result

# Example Usage
if __name__ == "__main__":
    root = TreeNode(3)
    root.left = TreeNode(4)
    root.right = TreeNode(5)
    root.left.left = TreeNode(6)
    root.left.right = TreeNode(7)
    root.right.right = TreeNode(8)

    print("Level Order Traversal (Recursive):")
    result = level_order_recursive(root)
    for level in result:
        print(level)
        

Iterative Approach

The iterative approach for level order traversal uses a queue to process nodes level by level. This method is more commonly used and efficient for large trees.

from collections import deque

# Iterative Level Order Traversal
def level_order_iterative(root):
    if not root:
        return []

    queue = deque([root])
    result = []

    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.value)

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

        result.append(level)
    return result

# Example Usage
if __name__ == "__main__":
    root = TreeNode(3)
    root.left = TreeNode(4)
    root.right = TreeNode(5)
    root.left.left = TreeNode(6)
    root.left.right = TreeNode(7)
    root.right.right = TreeNode(8)

    print("\nLevel Order Traversal (Iterative):")
    result = level_order_iterative(root)
    for level in result:
        print(level)
        

Conclusion

Both recursive and iterative approaches to level order traversal are useful to understand. The recursive method is elegant, but the iterative method is more practical and commonly used in real-world applications, especially for large trees.

Let us know which approach you prefer in the comments!