102. Binary Tree Level Order Traversal

Approach: BFS

We can use a queue to perform a level-order traversal of the binary tree. At each level, we process all nodes at that level before moving to the next level.

Algorithm:

Initialize a queue with the root node.
While the queue is not empty:
- Dequeue a node.
- Process the node (e.g., add its value to the result).
- Enqueue its left and right children (if they exist).
Return the result.

# 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 *

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

        qu = deque([root])

        ans = []
        while qu:
            level_size = len(qu)
            level = []

            for _ in range(level_size):
                node = qu.popleft()
                level.append(node.val)

                if node.left:
                    qu.append(node.left)
                if node.right:
                    qu.append(node.right)

            ans.append(level)

        return ans

Time: $O(n)$ — where $n$ is the number of nodes in the tree.
Space: $O(w)$ — the maximum width of the tree. The worst-case space complexity occurs when the tree is a complete binary tree, in which case the maximum width is $\frac{n}{2}$ , where $n$ is the number of nodes in the tree.

Last updated on

102. Binary Tree Level Order Traversal

Approach: BFS

On this page