Solutions

# DFS or BFS to traverse the tree level by level and collect the values of the nodes at each level in a list.
# trees

# DFS - O(n) time, O(n) space
def helper(root: TreeNode, level: int, res: List[List[int]]) -> None:
    if root is None:
        return

    if len(res) == level:
        res.append([])
    res[level].append(root.val)
    helper(root.left, level+1, res)
    helper(root.right, level+1, res)
    

def levelOrder1(root: TreeNode) -> List[List[int]]:
    res = []
    helper(root, 0, res)
    return res
    
# BFS - O(n) time, O(n) space
def levelOrder(root: TreeNode) -> List[List[int]]:
    from collections import deque
    
    q = deque()
    q.append(root)
    res = []

    while q:
        qlen = len(q)
        level = []

        for _ in range(qlen):
            node = q.popleft()
            if node:
                level.append(node.val)
                q.append(node.left)
                q.append(node.right)

        if level:
            res.append(level)
    return res