8.3 Breadth-First Search Traversal
Breadth-first search (BFS) visits a tree level by level.
8.3 Breadth-First Search Traversal
Breadth-first search (BFS) visits a tree level by level. It starts at the root, visits all nodes at depth 1, then all nodes at depth 2, and continues outward until every reachable node has been processed.
DFS follows one branch as far as possible before returning. BFS expands evenly across the tree. That difference makes BFS the natural choice when distance from the root matters, when you need shortest paths in an unweighted tree, or when the output must be grouped by depth.
Problem
You need to visit every node in a tree by increasing distance from the root.
Solution
Use a queue.
For a rooted tree represented by child lists:
package main
import "fmt"
func bfs(tree [][]int, root int) {
queue := []int{root}
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
fmt.Println(node)
for _, child := range tree[node] {
queue = append(queue, child)
}
}
}
For this tree:
0
├── 1
│ ├── 3
│ └── 4
└── 2
├── 5
└── 6
the output is:
0
1
2
3
4
5
6
The traversal visits nodes in nondecreasing depth order.
For an undirected tree, store the parent or maintain a visited array:
func bfsUndirected(adj [][]int, root int) {
parent := make([]int, len(adj))
for i := range parent {
parent[i] = -1
}
queue := []int{root}
parent[root] = root
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
fmt.Println(node)
for _, next := range adj[node] {
if parent[next] != -1 {
continue
}
parent[next] = node
queue = append(queue, next)
}
}
}
The parent array prevents the traversal from walking back to already discovered nodes. It also records the BFS tree.
Discussion
BFS uses a first-in, first-out queue. Nodes discovered earlier are processed earlier. Since children of depth d nodes are discovered before any depth d + 2 node can be reached, the queue preserves level order.
This property is useful enough that BFS is often the simplest correct algorithm for distance problems on unweighted trees.
To compute depth from the root:
func depths(adj [][]int, root int) []int {
depth := make([]int, len(adj))
for i := range depth {
depth[i] = -1
}
queue := []int{root}
depth[root] = 0
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
for _, next := range adj[node] {
if depth[next] != -1 {
continue
}
depth[next] = depth[node] + 1
queue = append(queue, next)
}
}
return depth
}
Each node receives its depth when it is first discovered. In a tree, there is exactly one simple path from the root to any node, so the first discovery gives the true distance.
Avoiding Slow Queue Operations
The previous examples use:
node := queue[0]
queue = queue[1:]
This is clear, but for long-running programs it can keep references to old elements and may delay garbage collection. A more controlled queue uses a head index:
func bfsWithHeadIndex(tree [][]int, root int) {
queue := []int{root}
head := 0
for head < len(queue) {
node := queue[head]
head++
fmt.Println(node)
for _, child := range tree[node] {
queue = append(queue, child)
}
}
}
This version avoids repeatedly reslicing the queue. It is a common Go pattern for BFS.
Level-by-Level Processing
Some problems require processing one depth level at a time. For example, you may need the average value at each level, the rightmost node at each level, or the width of the tree.
Use the current queue length to isolate one level:
func levels(tree [][]int, root int) [][]int {
result := [][]int{}
queue := []int{root}
for len(queue) > 0 {
levelSize := len(queue)
level := make([]int, 0, levelSize)
for i := 0; i < levelSize; i++ {
node := queue[0]
queue = queue[1:]
level = append(level, node)
for _, child := range tree[node] {
queue = append(queue, child)
}
}
result = append(result, level)
}
return result
}
For the sample tree, this returns:
[[0] [1 2] [3 4 5 6]]
This pattern is simple and reliable. The queue contains exactly one frontier at the start of each outer-loop iteration.
BFS on Binary Trees
For pointer-based binary trees, the same queue idea applies:
type Node struct {
Value int
Left *Node
Right *Node
}
func bfsBinary(root *Node) {
if root == nil {
return
}
queue := []*Node{root}
head := 0
for head < len(queue) {
node := queue[head]
head++
fmt.Println(node.Value)
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
}
The explicit nil check at the beginning handles empty trees. Child checks prevent nil pointers from entering the queue.
Reconstructing Paths
BFS can also record parents so that paths can be reconstructed.
func pathFromRoot(adj [][]int, root, target int) []int {
parent := make([]int, len(adj))
for i := range parent {
parent[i] = -1
}
queue := []int{root}
head := 0
parent[root] = root
for head < len(queue) {
node := queue[head]
head++
if node == target {
break
}
for _, next := range adj[node] {
if parent[next] != -1 {
continue
}
parent[next] = node
queue = append(queue, next)
}
}
if parent[target] == -1 {
return nil
}
path := []int{}
for current := target; current != root; current = parent[current] {
path = append(path, current)
}
path = append(path, root)
for left, right := 0, len(path)-1; left < right; left, right = left+1, right-1 {
path[left], path[right] = path[right], path[left]
}
return path
}
In a valid tree, the target is reachable from the root if the tree is connected. The nil return still helps when the same function is used on general graphs or malformed input.
Complexity Analysis
For a tree with n nodes:
| Operation | Complexity |
|---|---|
| BFS traversal | O(n) |
| Depth computation | O(n) |
| Parent reconstruction | O(n) |
| Queue memory | O(w) |
Here w is the maximum width of the tree, meaning the largest number of nodes held in the queue at one time.
A DFS stack depends on height. A BFS queue depends on width. In a balanced binary tree, the last level may contain about half the nodes, so BFS can use O(n) memory even when DFS uses only O(log n) stack space.
Common Mistakes
A frequent bug is marking a node as visited too late. Mark it when it is enqueued, not when it is dequeued. Otherwise the same node may be added to the queue multiple times in general graphs.
This is the safe pattern:
if depth[next] == -1 {
depth[next] = depth[node] + 1
queue = append(queue, next)
}
Another mistake is using BFS when postorder information is required. BFS is good for level order and distance from the root. It is usually a poor fit when a parent depends on values computed from all descendants. Subtree sizes, heights, and dynamic programming on trees usually want DFS.
A third mistake is using queue = queue[1:] in performance-sensitive code without thinking about memory retention. For most small problems it is fine. For large workloads, prefer a head index or a dedicated queue type.
Takeaway
Breadth-first search processes a tree in increasing distance from the root. Use it for level-order traversal, shortest paths in unweighted trees, depth computation, and problems where each level must be handled as a group. The queue is the key data structure: it stores the current frontier and guarantees that nearer nodes are processed before farther nodes.