Binary Tree Level Order Traversal

The problem description can be found in LeetCode.

Approach

This is a perfect example to apply BFS, since it is a level-by-level traversal by definition (first solution).

DFS can be applied too, but you also need to keep track of the current level (second solution).

Solution

from collections import deque
from typing import List, Optional


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

        queue = deque([root])
        ans: List[List[int]] = []
        level = 0
        while queue:
            ans.append([])

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

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

            level += 1

        return ans

from collections import deque
from typing import List, Optional


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

        queue = deque([root])
        ans: List[List[int]] = []
        level = 0
        while queue:
            ans.append([])

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

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

            level += 1

        return ans

Complexity

• Time: $O(n)$
• Space: $O(n)$

Where $n$ is the number of nodes in the tree.