Binary Tree Level Order Traversal - Leetcode Solution

The problem statement is as follows:

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Approach:

The problem can be easily solved using BFS. We can traverse the tree level by level and store the nodes on each level in a list. We can then add the list to a final result list which contains the level order traversal of the tree.

Algorithm:

1. Create an empty queue and add the root node to it.

2. While the queue is not empty, repeat steps 3 to 5.

3. Dequeue a node from the queue and add its value to the current level list.

4. Enqueue the left and right child of the dequeued node if they exist.

5. If the current level has been fully traversed, add the current level list to the final result list, and reset the current level list to an empty list.

6. Return the final result list.

Code:

from collections import deque

def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
    if not root:
        return []
    
    result = []
    queue = deque()
    queue.append(root)
    
    while queue:
        current_level = []
        level_size = len(queue)
        
        for i 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

Time Complexity:

The time complexity of the above algorithm is O(N) where N is the number of nodes in the binary tree. We visit each node only once in the worst case.

Space Complexity:

The space complexity of the above algorithm is O(N) where N is the number of nodes in the binary tree. In the worst case, when the tree is a complete binary tree, the maximum size of the queue would be (N/2)+1. Therefore, the space complexity of the algorithm is also O(N).

1