Breadth-First Search (BFS) in Go

Suppose you’re given a binary tree implemented somewhat like this:

type TreeNode[T comparable] struct {
    Val T
    Left *TreeNode
    Right *TreeNode
}

type TreeNode[T comparable] struct {
    Val T
    Left *TreeNode
    Right *TreeNode
}

Breadth-First Search (BFS) means you traverse the tree level by level, not diving deep into a child node every chance you get.

The blocker here is not knowing how to link all nodes belonging to the same level, because in a binary tree, same-level nodes are not all linked, except the two siblings under the same parent.

We need an auxiliary data structure.

Suppose we can have all nodes on the same level tracked in a single data structure; what property would you want this structure to have?

If you ask me, I’d like it to allow me to track the nodes in whatever order I set, and when I retrieve them from the structure, I’d want them in the exact same order.

That screams First-In, First-Out (FIFO), or in other words, a queue.

func BFS[T comparable](root *TreeNode[T], target T) *TreeNode[T] {
     if root == nil {
         return nil
     }
     
     queue := []*TreeNode[T]{ root }
     
     for len(queue) > 0 {
         // dequeue
         node := queue[0]
         queue = queue[1:]
         
         if node.Val == target {
             return node
         }
         
         // add children to the queue
         // all nodes on current level have been there before
         if node.Left != nil {
             queue = append(queue, node.Left)
         }
         if node.Right != nil {
             queue = append(queue, node.Right)
         }
     }
     
     return nil
}

func BFS[T comparable](root *TreeNode[T], target T) *TreeNode[T] {
     if root == nil {
         return nil
     }
     
     queue := []*TreeNode[T]{ root }
     
     for len(queue) > 0 {
         // dequeue
         node := queue[0]
         queue = queue[1:]
         
         if node.Val == target {
             return node
         }
         
         // add children to the queue
         // all nodes on current level have been there before
         if node.Left != nil {
             queue = append(queue, node.Left)
         }
         if node.Right != nil {
             queue = append(queue, node.Right)
         }
     }
     
     return nil
}

The generic type T implements comparable because it allows == and != operators, which is what BFS requires.

BFS is not searching a Binary Search Tree (BST)!

• BFS works on any binary tree; while a BST must be ordered.
• BFS is $O(n)$ time, $O(n)$ space; while searching a BST is $O(log n)$ time if balanced, and $O(1)$ space.

In fact, if a binary tree is ordered and balanced, you should never use BFS to search it.