Breadth-First Search explores a tree level by level using a queue. It enqueues the root, then repeatedly dequeues a node, visits it, and enqueues its children. Because nodes are processed in arrival order, BFS guarantees that when it first reaches a node it has found the shortest path from the root.
| 1 | from collections import deque |
| 2 | def bfs(root): |
| 3 | queue = deque([root]) |
| 4 | while queue: |
| 5 | node = queue.popleft() |
| 6 | print(node.val) |
| 7 | if node.left: queue.append(node.left) |
| 8 | if node.right: queue.append(node.right) |