Notes

Binary Tree BFS Techniques

Breadth-First Search (BFS) is a fundamental algorithm used to traverse or search tree or graph data structures. In the context of binary trees, BFS is often referred to as level-order traversal because it visits all nodes at each level of the tree before moving to the next level.

Key Concepts

1. Queue: BFS uses a queue to keep track of nodes at the current level before moving to the next level.
2. Level by Level Traversal: Nodes are processed level by level, starting from the root.
3. First In, First Out (FIFO): Nodes are added to the queue in the order they are encountered and processed in the same order.

Steps

1. Initialize: Start with a queue containing the root node.
2. Process: Dequeue a node, process it, and enqueue its children.
3. Repeat: Continue until the queue is empty, indicating that all nodes have been processed.

Applications

1. Level Order Traversal: Printing or collecting nodes level by level.
2. Finding the Depth/Height: Calculating the maximum depth or height of the tree.
3. Shortest Path in Unweighted Trees: Finding the shortest path in terms of number of edges from the root to any node.
4. Checking Completeness: Determining if a binary tree is complete.

Example: Level Order Traversal

Problem: Traverse the binary tree level by level and print each level.

Code:

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def level_order_traversal(root):
    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

# Example usage:
# Constructing the binary tree
#       3
#      / \
#     9   20
#        /  \
#       15   7
tree = TreeNode(3)
tree.left = TreeNode(9)
tree.right = TreeNode(20, TreeNode(15), TreeNode(7))

print(level_order_traversal(tree))  # Output: [[3], [9, 20], [15, 7]]

Explanation:

1. Initialize: A queue is initialized with the root node.
2. Process: Nodes are dequeued one by one. Their values are collected, and their children are enqueued.
3. Level by Level: The process repeats until the queue is empty, resulting in a list of lists where each sublist contains nodes at the same level.

Example: Finding Maximum Depth

Problem: Calculate the maximum depth (height) of a binary tree.

Code:

from collections import deque

def max_depth_bfs(root):
    if not root:
        return 0

    queue = deque([root])
    depth = 0

    while queue:
        depth += 1
        level_size = len(queue)

        for _ in range(level_size):
            node = queue.popleft()

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

    return depth

# Example usage:
print(max_depth_bfs(tree))  # Output: 3

Explanation:

1. Initialize: A queue is initialized with the root node and depth is set to 0.
2. Process: Nodes are dequeued level by level, and the depth counter is incremented after processing each level.
3. Depth Calculation: The process repeats until the queue is empty, resulting in the maximum depth of the tree.

Summary of BFS Techniques in Binary Trees

• Level Order Traversal: Collecting or printing nodes level by level using a queue.
• Finding Maximum Depth: Using BFS to determine the maximum depth by processing nodes level by level.
• Shortest Path in Unweighted Trees: BFS naturally finds the shortest path in terms of edges from the root to any node.
• Checking Completeness: Ensuring that all levels of the tree are fully filled except possibly the last level, which should be filled from left to right.

Advantages of BFS

• Simple and Intuitive: Easy to understand and implement using a queue.
• Level by Level Processing: Ideal for problems that require processing nodes level by level.
• Shortest Path: Naturally finds the shortest path in unweighted trees or graphs.

When to Use BFS

• When you need to process nodes level by level.
• When finding the shortest path in an unweighted graph or tree.
• When calculating metrics that depend on levels, such as the maximum depth or checking the completeness of a tree.

1. 200. Number of Islands

Problem:

Given a 2D grid of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

Approach (BFS):

• Use Breadth-First Search (BFS) to explore each island. Start BFS whenever you encounter '1', mark all connected '1's as visited (by changing them to '0'), and increment the island count.

Python Code:

Certainly! Here is the code with comments explaining each step.

1. 200. Number of Islands

from collections import deque

def numIslands(grid: List[List[str]]) -> int:
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    island_count = 0

    # BFS function to traverse the island
    def bfs(r, c):
        queue = deque([(r, c)])
        while queue:
            row, col = queue.popleft()
            # Check boundaries and if the current cell is part of an island
            if 0 <= row < rows and 0 <= col < cols and grid[row][col] == '1':
                grid[row][col] = '0'  # Mark as visited by setting to '0'
                # Add all neighboring cells (up, down, left, right) to the queue
                queue.extend([(row-1, col), (row+1, col), (row, col-1), (row, col+1)])

    # Iterate over each cell in the grid
    for r in range(rows):
        for c in range(cols):
            # If the cell is a '1', start BFS to mark the entire island
            if grid[r][c] == '1':
                bfs(r, c)
                island_count += 1  # Increase island count for each BFS

    return island_count  # Return the total number of islands found

Example:

grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
print(numIslands(grid))  # Output: 1

Explanation:

• We start BFS whenever we find an unvisited '1' and mark all connected lands as visited by changing them to '0'.
• The BFS continues until all parts of the island are explored.
• This continues for each island found, resulting in the total count.

2. 339. Nested List Weight Sum

Problem:

Given a nested list of integers, return the sum of all integers in the list weighted by their depth. For example, [1,[4,[6]]] would return 1*1 + 4*2 + 6*3 = 27.

Approach (BFS):

• Use a Breadth-First Search (BFS) approach to traverse the nested list and calculate the weighted sum by tracking the depth level of each element.

Python Code:

from collections import deque

def depthSum(nestedList: List[NestedInteger]) -> int:
    queue = deque([(nestedList, 1)])  # Queue stores (list, depth) pairs
    total_sum = 0

    # BFS loop to process each element in the queue
    while queue:
        current_list, depth = queue.popleft()
        for element in current_list:
            if element.isInteger():
                # If it's an integer, add to the total sum weighted by depth
                total_sum += element.getInteger() * depth
            else:
                # If it's a list, add it to the queue with increased depth
                queue.append((element.getList(), depth + 1))

    return total_sum  # Return the weighted sum of all integers

Example:

nestedList = [NestedInteger(1), NestedInteger([NestedInteger(4), NestedInteger([NestedInteger(6)])])]
print(depthSum(nestedList))  # Output: 27

Explanation:

• The BFS traverses the nested list level by level.
• Each integer’s contribution to the sum is calculated based on its depth, which is tracked as we traverse each level.

3. 827. Making A Large Island

Problem:

You are given an n x n binary grid. You can change exactly one 0 to 1. Find the largest island size you can create by making this change.

Approach (BFS):

• First, identify all islands using BFS, and assign unique island identifiers.
• Then, for each 0 in the grid, check its neighboring islands and calculate the possible new island size by merging these islands.
• Track the maximum possible island size.

Python Code:

from collections import deque, defaultdict

def largestIsland(grid: List[List[int]]) -> int:
    n = len(grid)
    island_size = defaultdict(int)  # Dictionary to store island sizes
    island_id = 2  # Start with an island id of 2 to distinguish from 1 and 0

    # BFS function to determine the size of each island
    def bfs(r, c, island_id):
        queue = deque([(r, c)])
        size = 0
        while queue:
            row, col = queue.popleft()
            if 0 <= row < n and 0 <= col < n and grid[row][col] == 1:
                grid[row][col] = island_id  # Mark as part of the current island
                size += 1  # Increment the size of the island
                # Add neighboring cells to the queue
                queue.extend([(row-1, col), (row+1, col), (row, col-1), (row, col+1)])
        return size

    # First pass: assign ids to islands and record sizes
    for r in range(n):
        for c in range(n):
            if grid[r][c] == 1:  # If it's part of an island
                island_size[island_id] = bfs(r, c, island_id)
                island_id += 1

    # Second pass: check every 0 cell and calculate potential island size
    max_island = max(island_size.values(), default=0)  # Start with the largest existing island
    for r in range(n):
        for c in range(n):
            if grid[r][c] == 0:  # Consider flipping this 0 to a 1
                seen_islands = set()  # Track unique neighboring islands
                new_size = 1  # Start with size 1 for the flipped cell
                for nr, nc in [(r-1, c), (r+1, c), (r, c-1), (r, c+1)]:
                    if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] > 1:
                        seen_islands.add(grid[nr][nc])  # Add neighboring island ids
                new_size += sum(island_size[i] for i in seen_islands)  # Add sizes of all unique neighboring islands
                max_island = max(max_island, new_size)  # Update max island size if necessary

    return max_island  # Return the size of the largest possible island

Example:

grid = [
  [1, 0],
  [0, 1]
]
print(largestIsland(grid))  # Output: 3

Explanation:

• The BFS first identifies all islands and calculates their sizes.
• We then evaluate the effect of converting each 0 to 1, merging adjacent islands, and keeping track of the maximum island size.

4. 1091. Shortest Path in Binary Matrix

Problem:

Given a binary matrix, return the length of the shortest clear path from the top-left corner to the bottom-right corner. If such a path does not exist, return -1. The path can only move in 8 possible directions.

Approach (BFS):

• Use BFS to explore all possible paths starting from the top-left corner. The first time you reach the bottom-right corner, the length of the path is the answer.

Python Code:

from collections import deque

def rightSideView(root: TreeNode) -> List[int]:
    if not root:
        return []

    view = []  # List to store the rightmost nodes
    queue = deque([root])  # Start BFS with the root

    while queue:
        level_length = len(queue)  # Number of nodes at the current level
        for i in range(level_length):
            node = queue.popleft()
            if i == level_length - 1:  # If it's the last node in the current level
                view.append(node.val)  # Add it to the view

            if node.left:
                queue.append(node.left)  # Add left child to the queue
            if node.right:
                queue.append(node.right)  # Add right child to the queue

    return view  # Return the list of rightmost nodes

Example:

grid = [
  [0, 1],
  [1, 0]
]
print(shortestPathBinaryMatrix(grid))  # Output: 2

Explanation:

• BFS explores all paths level by level. The first time the BFS reaches the bottom-right corner, it returns the path length as the answer.
• This guarantees the shortest path is found.

5. 199. Binary Tree Right Side View

Problem:

Given a binary tree, return the values of the nodes you can see when looking at the tree from the right side.

Approach (BFS):

• Use BFS to traverse the tree level by level, and take the last node of each level, as it represents the rightmost node visible from the right side.

Python Code:

6. 133. Clone Graph

from collections import deque

def cloneGraph(node: 'Node') -> 'Node':
    if not node:
        return None

    clones = {node: Node(node.val)}  # Dictionary to keep track of cloned nodes
    queue = deque([node])  # BFS queue starting with the original node

    # BFS loop to clone the graph
    while queue:
        current = queue.popleft()
        for neighbor in current.neighbors:
            if neighbor not in clones:  # If the neighbor hasn't been cloned yet
                clones[neighbor] = Node(neighbor.val)  # Clone the neighbor
                queue.append(neighbor)  # Add the original neighbor to the queue
            clones[current].neighbors.append(clones[neighbor])  # Link the clone of the current node to the clone of the neighbor

    return clones[node]  # Return the clone of the original node

7. 102. Binary Tree Level Order Traversal

from collections import deque

def levelOrder(root: TreeNode) -> List[List[int]]:
    if not root:
        return []

    result = []  # List to store the level order traversal
    queue = deque([root])  # Start BFS with the root

    # BFS loop to traverse the tree level by level
    while queue:
        level = []
        level_length = len(queue)  # Number of nodes at the current level
        for _ in range(level_length):
            node = queue.popleft()
            level.append(node.val)  # Add the node's value to the current level