Breadth-First Search (BFS) for Trees

Breadth-First Search (BFS) is an algorithm for traversing or searching tree or graph data structures. It explores the neighbor nodes first, before moving to the next level neighbors.

Interactive BFS Traversal Visualization

The visualization below demonstrates the BFS traversal process on a sample tree. You can see how the algorithm explores the tree level by level.

BFS Traversal (Tree)

Step 1 of 0

Action

Ready to start

Current Node

None

Queue

[]

Traversal Order

[]

Current Node

Visited

In Queue

Unvisited

Breadth-First Search (BFS) Algorithm

Breadth-First Search (BFS) is a tree and graph traversal algorithm that explores neighbor nodes first, before moving to the next level neighbors. It's also known as a level-order traversal, as it visits nodes level by level.

Algorithm Steps

Create a queue and add the root node to it.
While the queue is not empty, do the following:
Dequeue a node and process it (e.g., add its value to a list).
Enqueue its left child, if it exists.
Enqueue its right child, if it exists.
Repeat until the queue is empty.

BFS (Level-Order) Traversal


from collections import deque

# 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
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
            
        res = []
        q = deque([root])
        
        while q:
            level_size = len(q)
            level = []
            for _ in range(level_size):
                node = q.popleft()
                level.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            res.append(level)
            
        return res