# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from collections import deque

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        '''
        BFS
        '''
        
        if root is None: return []
        
        q = deque([root])
        results = []
        
        while q:
            n = len(q)
            
            level = []
            # Idea here is we iterate through the queue, the queue
            # will always contain 1, 2, 4, 8 ... elements for each
            # level since we'll be appending None .left/.right nodes
            # also. This makes it easier to do the computation.
            for i in range(n):
                curr = q.popleft()
                
                # Could be None, ignore if that's the case
                if curr:
                    level.append(curr.val)
                    
                    # It's okay to append None values here, the condition
                    # above will filter it out
                    q.append(curr.left)
                    q.append(curr.right)
            
            # Since there's a chance that at the last level of the tree, we
            # might be pushing None nodes due to .left/.right being None, we
            # might have an empty level. We check and avoid adding the empty
            # level in this case.
            if level:
                results.append(level)
        
        return results