DEV Community

Shahrouz Nikseresht
Shahrouz Nikseresht

Posted on

Day 65: Python Breadth-First Search (BFS) on Tree, Queue-Based Level-Order Traversal for Shortest Path and Layer Exploration

#challenge #python #datastructures #algorithms

Welcome to Day 65 of the #80DaysOfChallenges journey! This intermediate challenge implements Breadth-First Search (BFS) on a tree structure using a queue for level-by-level traversal, deque from collections for efficient FIFO operations, and a visited list for order tracking, achieving O(n) time where n is nodes. It's a foundational graph algorithm for level-order exploration, shortest path in unweighted graphs, or layer-based processing, common in tree problems like finding minimum depth or level averages. If you're advancing from basic trees to queue-based algos or prepping for interviews with BFS variants (LeetCode #102 style), this "Python BFS on tree" script demonstrates a function that's clean, handles dict adjacency, and easy to adapt for graphs with cycles or weighted edges.

💡 Key Takeaways from Day 65: BFS Traversal Function

This task features a function that uses a deque queue to enqueue children and popleft for FIFO order, ensuring level-by-level visit. It's a standard BFS pattern: queue start, dequeue/visit/enqueue neighbors. We'll detail: function with queue and visited, loop for dequeue and enqueue, and example tree with main print.

1. Function Design: Queue and Visited Setup

The bfs function takes tree dict and start, returns traversal list:

def bfs(tree: dict, start):
    """Perform BFS traversal starting from the given node."""
    visited = []                    # store traversal order
    queue = deque([start])          # queue for BFS (FIFO)
Enter fullscreen mode Exit fullscreen mode

Visited records order, deque starts with root for FIFO levels. Deque efficient for append/popleft O(1).

2. Loop Processing: Dequeue, Visit, Enqueue Children

Core while processes queue:

    while queue:
        node = queue.popleft()      # take next node from the front

        if node not in visited:
            visited.append(node)    # mark node as visited

            # enqueue children in natural order (left to right)
            for child in tree.get(node, []):
                queue.append(child)

    return visited
Enter fullscreen mode Exit fullscreen mode

Popleft dequeues, append to visited if new. Enqueue children for level-order. tree.get(node, []) handles leaves. For tree A->B,C; B->D,E: order A, B, C, D, E, F.

3. Example Usage: Defined Tree and Print

Demo with dict tree:

tree = {
    "A": ["B", "C"],
    "B": ["D", "E"],
    "C": ["F"],
    "D": [],
    "E": [],
    "F": []
}

start_node = "A"                # starting point for BFS

print(f"Tree: {tree}")
print(f"Starting BFS from node: {start_node}")

traversal = bfs(tree, start_node)
print(f"BFS Traversal Order: {traversal}")
Enter fullscreen mode Exit fullscreen mode

Prints tree, runs BFS from A, shows A, B, C, D, E, F.

🎯 Summary and Reflections

This non-recursive BFS uses queue for level traversal efficiently. It reinforced:

  • Deque for FIFO: Popleft/append O(1), perfect for BFS.
  • Visited on dequeue: Ensures process once, order correct.
  • Get for children: Handles missing nodes gracefully.

Reflections: In trees no cycles, visited optional but good for graphs. Efficient O(n) time/space.

Advanced Alternatives: Recursive BFS with queue levels. Add level tracking. Graph with visited set. Your BFS tip? Share!

🚀 Next Steps and Resources

Day 65 conquered non-recursive BFS. In #80DaysOfChallenges? Added levels? Post!

Top comments (0)