deepSWE.io

Binary Tree Level Order Traversal

TreeBFSQueue

15 min

Problem Statement

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Example

Example 1:

Input: root = [3,9,20,null,null,15,7]

Output: [[3],[9,20],[15,7]]

Constraints

The number of nodes in the tree is in the range [0, 2000].
-1000 ≤ Node.val ≤ 1000

Solution (BFS with Queue)

The solution uses a queue to perform a Breadth-First Search (BFS). We traverse the tree level by level, adding the nodes of each level to a list.

Algorithm Steps

If the root is null, return an empty list.
Create a queue and add the root node.
While the queue is not empty, get the number of nodes at the current level.
Create a new list to store the nodes of the current level.
For each node at the current level, dequeue the node, add its value to the level list, and enqueue its children.
Add the level list to the result list.
After the loop, return the result list.

Start: Initialize queue with root (3).

Binary Tree Level Order Traversal Solution


# 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]]:
        if not root:
            return []
            
        result = []
        queue = deque([root])
        
        while queue:
            level_size = len(queue)
            level = []
            
            for _ in range(level_size):
                node = queue.popleft()
                level.append(node.val)
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            result.append(level)
            
        return result