Problem Statement

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).

Additional information

• The number of nodes in the tree is in the range [0, 2000].
• -1000 <= Node.val <= 1000

Example 1:

Input: root = [3, 9, 20, null, null, 15, 7]

Output: [[3], [9, 20], [15, 7]]

Example 2:

Input: root = [1]

Output: [[1]]

Example 3:

Input: root = []

Output: []

Iterative Breadth-First Search (BFS) - Optimal

Intuition

The most natural way to traverse a tree level by level is to use Breadth-First Search (BFS). BFS uses a Queue (First-In-First-Out).

To group the nodes by their level, we can process the queue in batches. At the start of each level, the number of nodes currently in the queue is exactly the number of nodes on that level. We can use a for loop to pop only that specific number of nodes, record their values in a sub-list, and push their children into the queue for the next level.

Algorithm

1. If the root is None, return an empty list [].
2. Initialize an empty list res to store the final result.
3. Initialize a queue and append the root.
4. While the queue is not empty:

• Get the current length of the queue (level_size = len(queue)).

• Create an empty list current_level to store values for this batch.

• Loop level_size times:

• Pop the leftmost node from the queue.

• Append its value to current_level.

• If it has a left child, append the left child to the queue.

• If it has a right child, append the right child to the queue.

• Append current_level to res.

5. Return res.

def level_order(root: Optional[TreeNode]) -> list[list[int]]:
    if not root:
        return []
        
    res = []
    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)
                
        res.append(current_level)
        
    return res

Time & Space Complexity

• Time complexity: O(n)

• Reason: Every node in the binary tree is pushed into and popped out of the queue exactly once.

• Space complexity: O(n)

• Reason: The queue can hold up to roughly n/2 nodes in the worst case (the bottom level of a perfect binary tree), and the result array holds exactly n elements. Thus, the space is proportional to n.

Recursive Depth-First Search (DFS)

Intuition

Although BFS is more intuitive for "level order", we can actually solve this using Depth-First Search (DFS).

The trick is to pass the current level (depth) as an argument in our recursive calls. We keep a global res list of lists. When we visit a node at level = L, we simply append its value to res[L]. If res doesn't have a sub-list for L yet (meaning this is the first time we've reached this depth), we append a new empty list to res before adding the value.

Algorithm

1. Initialize an empty list res.
2. Create a helper function dfs(node, level):

• If node is None, return.
• If len(res) == level, it means we haven't created a sub-list for this level yet. Append [] to res.
• Append node.val to res[level].
• Recursively call dfs(node.left, level + 1).
• Recursively call dfs(node.right, level + 1).

3. Call dfs(root, 0).
4. Return res.

def level_order(root: Optional[TreeNode]) -> list[list[int]]:
    res = []
    
    def dfs(node, level):
        if not node:
            return
            
        # If this is the first node we've seen at this level
        if len(res) == level:
            res.append([])
            
        res[level].append(node.val)
        
        dfs(node.left, level + 1)
        dfs(node.right, level + 1)
        
    dfs(root, 0)
    return res

Time & Space Complexity

• Time complexity: O(n)

• Reason: We visit every node in the tree exactly once.

• Space complexity: O(h)

• Reason: Excluding the output array, the space is taken by the recursion stack, which goes as deep as the height h of the tree. In the worst case, this is O(n).