Breadth-First Search (BFS)

from collections import deque

def level_order(root):
    """Return nodes level by level"""
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        current_level = []
        
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(current_level)
    
    return result

from collections import deque

def shortest_path(graph, start, end):
    """Find shortest path in unweighted graph"""
    if start == end:
        return 0
    
    queue = deque([(start, 0)])  # (node, distance)
    visited = {start}
    
    while queue:
        node, dist = queue.popleft()
        
        for neighbor in graph[node]:
            if neighbor == end:
                return dist + 1
            
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
    
    return -1  # No path found

from collections import deque

def shortest_path_grid(grid):
    """Find shortest path from top-left to bottom-right"""
    if not grid or grid[0][0] == 1:
        return -1
    
    rows, cols = len(grid), len(grid[0])
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    
    queue = deque([(0, 0, 1)])  # (row, col, distance)
    visited = {(0, 0)}
    
    while queue:
        r, c, dist = queue.popleft()
        
        if r == rows - 1 and c == cols - 1:
            return dist
        
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            
            if 0 <= nr < rows and 0 <= nc < cols:
                if grid[nr][nc] == 0 and (nr, nc) not in visited:
                    visited.add((nr, nc))
                    queue.append((nr, nc, dist + 1))
    
    return -1

from collections import deque

def walls_and_gates(rooms):
    """Fill each empty room with distance to nearest gate"""
    if not rooms:
        return
    
    INF = 2147483647
    GATE = 0
    rows, cols = len(rooms), len(rooms[0])
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    
    # Start BFS from all gates simultaneously
    queue = deque()
    for r in range(rows):
        for c in range(cols):
            if rooms[r][c] == GATE:
                queue.append((r, c))
    
    while queue:
        r, c = queue.popleft()
        
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            
            if 0 <= nr < rows and 0 <= nc < cols:
                if rooms[nr][nc] == INF:  # Empty room
                    rooms[nr][nc] = rooms[r][c] + 1
                    queue.append((nr, nc))

from collections import deque

def word_ladder(begin_word, end_word, word_list):
    """Find shortest transformation sequence length"""
    word_set = set(word_list)
    if end_word not in word_set:
        return 0
    
    queue = deque([(begin_word, 1)])
    visited = {begin_word}
    
    while queue:
        word, length = queue.popleft()
        
        if word == end_word:
            return length
        
        # Try changing each character
        for i in range(len(word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                new_word = word[:i] + c + word[i+1:]
                
                if new_word in word_set and new_word not in visited:
                    visited.add(new_word)
                    queue.append((new_word, length + 1))
    
    return 0