Tree Breadth-First Search

A queue processes one level at a time

Breadth-first search uses a queue (collections.deque). Recording the queue length at the start of each loop lets you process exactly one level, which solves level-order traversal, right-side view, minimum depth and zigzag order. BFS finds the shallowest node first, so it suits "minimum depth" questions.

Level order and right-side view, run

I ran this with Python 3.12.3 (standard library only). Levels are collected separately; the last value of each level is the right-side view; an empty tree returns an empty list.

# Tree BFS: level-order traversal and right-side view
from collections import deque

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

def levels(root):
    out, q = [], deque([root] if root else [])
    while q:
        level = []
        for _ in range(len(q)):          # process exactly one level
            n = q.popleft()
            level.append(n.val)
            q.extend(c for c in (n.left, n.right) if c)
        out.append(level)
    return out

root = T(3, T(9), T(20, T(15), T(7)))
lv = levels(root)
print(lv)
print("right side view:", [level[-1] for level in lv])
print(levels(None))

Output:

[[3], [9, 20], [15, 7]]
right side view: [3, 20, 7]
[]

Use deque, not list.pop(0)

list.pop(0) is O(n); deque.popleft() is O(1).

त्वरित जाँच: Which data structure drives BFS?

• A queue
• A stack
• A heap
• A hash set only