program for level order traversal code example

Example: Level order traversal of binary tree

# To import queue datastructure
import collections
 
# Code to implement a binary tree
class TreeNode: 
     def __init__(self, val):
         self.val = val
         self.left = None
         self.right = None
 
# Function for level Order Traversal
def levelOrderTraversal(root):
    ans = []
 
    # Return Null if the tree is empty
    if root is None:
        return ans
    
    # Initialize queue 
    queue = collections.deque()
    queue.append(root)
 
    # Iterate over the queue until it's empty
    while queue:
        # Check the length of queue
        currSize = len(queue)
        currList = []
 
        while currSize > 0:
            # Dequeue element
            currNode = queue.popleft()
            currList.append(currNode.val)
            currSize -= 1
 
            # Check for left child
            if currNode.left is not None:
                queue.append(currNode.left)
            # Check for right child
            if currNode.right is not None:
                queue.append(currNode.right)
        
        # Append the currList to answer after each iteration
        ans.append(currList)
 
    # Return answer list
    return ans
 
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
 
# Check if the algorithm work
print(levelOrderTraversal(root))