BFS for Trees

The BFS algorithm uses a queue to process all the nodes level-by-level in a tree:

from typing import List, Optional


class TreeNode:
    def __init__(self, val,
                 left: Optional['TreeNode'] = None,
                 right: Optional['TreeNode'] = None) -> None:
        self.val = val
        self.left = left
        self.right = right


from collections import deque
from typing import Deque, List, Optional


class Solution:
    def levelOrder(self, root: Optional[TreeNode] = None) -> List[List[int]]:
        res = []

        queue: Deque[int] = deque([])
        if root:
            queue.append(root)

        while queue:
            res_level = []
            for _ in range(len(queue)):
                node = queue.popleft()
                res_level.append(node.val)

                for child in [node.left, node.right]:
                    if child:
                        queue.append(child)

            res.append(res_level)

        return res

The DFS algorithm can also be used for a level-by-level traversal, even if it is less intuitive than using a queue:

from typing import List, Optional


class TreeNode:
    def __init__(self, val,
                 left: Optional['TreeNode'] = None,
                 right: Optional['TreeNode'] = None) -> None:
        self.val = val
        self.left = left
        self.right = right


from typing import List, Optional


class Solution:
    def levelOrder(self, root: Optional[TreeNode] = None) -> List[List[int]]:
        def dfs(level: int, node: Optional[TreeNode] = None) -> None:
            if not node:
                return

            nonlocal res
            if len(res) == level:
                res.append([])

            res[level].append(node.val)

            for child in [node.left, node.right]:
                if child:
                    dfs(level + 1, child)

        res = []
        dfs(0, root)

        return res

Both solutions can be tested in LeetCode.