To solve the “Binary Tree Level Order Traversal” problem, we can perform a level order traversal using a queue. We traverse the tree level by level, enqueueing each node’s children in the order they appear.

from typing import List
from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def level_order_traversal(root: TreeNode) -> List[List[int]]:
    if not root:
    	# Return an empty list for an empty tree
        return []

    # List to store the final result
    result = []
    # Use a deque to efficiently perform enqueue and dequeue operations
    queue = deque([root])

    while queue:
    	# Get the number of nodes at the current level
        level_size = len(queue)
        # List to store values of nodes at the current level
        level_nodes = []

        for _ in range(level_size):
        	# Dequeue the front node
            node = queue.popleft()
            # Add the value of the current node to the current level list
            level_nodes.append(node.val)

            if node.left:
            	# Enqueue the left child if it exists
                queue.append(node.left)
            if node.right:
            	# Enqueue the right child if it exists
                queue.append(node.right)

		# Add the list of values at the current level to the result list
        result.append(level_nodes)

    return result

# Example usage:
root = TreeNode(3, 
	            TreeNode(9), 
	            TreeNode(20, 
	            	     TreeNode(15), 
	            	     TreeNode(7)
	            	     )
	            )

result = level_order_traversal(root)
print(result)
assert result == [[3], [9, 20], [15, 7]]

Explanation:

  • The level_order_traversal function uses a queue to perform level order traversal.
  • We start with the root node and enqueue it.
  • While the queue is not empty, we process each level by dequeuing nodes and enqueuing their children.
  • We keep track of the size of the current level to ensure that we process only the nodes at the current level.
  • The values of nodes at each level are appended to the result list.

Time Complexity:

The time complexity is O(N), where N is the number of nodes in the binary tree. We visit each node once during the traversal.

Space Complexity:

The space complexity is O(W), where W is the maximum width of the tree (maximum number of nodes at any level). In the worst case, the width of the tree is at most N/2, so the space complexity is also O(N).