Python Program to Perform Level Order Traversal on a Binary Tree

This program demonstrates how to perform a level order traversal on a binary tree using a queue. This traversal technique visits each level of the tree from left to right and from top to bottom, ensuring that each node at a particular depth is processed before moving to the next level.

from collections import deque

class TreeNode:
    """Definition of a binary tree node."""
    def __init__(self, x):
        """
        Initialize a tree node with a value.
        
        :param x: int, the integer value of the node
        """
        self.val = x
        self.left = None
        self.right = None

def levelOrder(root):
    """
    Perform level order traversal of a binary tree.

    :param root: TreeNode, the root of the binary tree
    :return: List[List[int]], a list of lists containing the values of the nodes at each level
    """
    if not root:
        return []
    
    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        current_level = []
        
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(current_level)

    return result

# Example Usage
if __name__ == "__main__":
    # Construct a simple tree
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.right = TreeNode(3)
    root.left.left = TreeNode(4)
    root.left.right = TreeNode(5)
    root.right.right = TreeNode(6)

    # Perform level order traversal
    levels = levelOrder(root)
    print("Level order traversal of the tree:", levels)

The program defines a TreeNode class for the structure of the binary tree nodes and a function levelOrder to carry out the level order traversal. The function initializes a queue with the root node and iteratively processes each level of the tree, capturing the values in a list. This method ensures all nodes at the current depth are processed before moving on to the next depth, perfectly reflecting the behavior of level order traversal.