algoadvance

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

Example

Example 1:

Input:

       3
      / \
     9   20
        /  \
       15   7

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

Example 2:

Input:

    1
   / \
  2   3
 / \
4   5

Output: [[1], [2, 3], [4, 5]]

Constraints:

Clarifying Questions

  1. What if the tree is empty?
    • If the tree is empty, the root node will be None, and the function should return an empty list [].
  2. Are there any specific conditions on the tree structure?
    • No, the tree can be any binary tree without additional constraints.
  3. Should the result list of lists maintain the order of elements as they appear at each level?
    • Yes, the order of elements should be from left to right for each level.

Strategy

To achieve a level order traversal, we can use a queue data structure to perform a breadth-first search (BFS). The BFS approach will help in processing nodes level by level from left to right. Here’s a step-by-step breakdown:

  1. Initialization:
    • If the root is None, return an empty list [].
    • Initialize an empty list result to store the level order traversal.
    • Use a queue initialized with the root node.
  2. Iteration:
    • While the queue is not empty:
      • Determine the number of nodes at the current level (level_size).
      • Initialize an empty list current_level to store the values of nodes at the current level.
      • For each node at the current level:
        • Pop the node from the front of the queue.
        • Append its value to current_level.
        • Add its left and right children (if they exist) to the queue.
      • Append current_level to result.
  3. Return the result:
    • Once the queue is empty, return result containing the level order traversal.

Code

from collections import deque
from typing import List, Optional

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

def levelOrder(root: Optional[TreeNode]) -> List[List[int]]:
    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

Time Complexity

Try our interview co-pilot at AlgoAdvance.com