Binary Tree Breadth-First Search (BFS) Traversal using a queue in Go (GoLang).

binarytree-traversals-bfs.go

package binarytree

// Tree is a binary tree.
type Tree struct {
	Root *Node
}

// Node is a binary tree node.
type Node struct {
	Val   int
	Left  *Node
	Right *Node
}

// BFSTraversal uses Breadth-First Search (BFS)
// to traverse of the tree nodes.
func BFSTraversal(t *Tree) []int {
	sol := make([]int, 0)
	if t == nil || t.Root == nil {
		return sol
	}
	queue := NewQueue()
	queue.Enqueue(t.Root)

	for !queue.IsEmpty() {
		curr := queue.Dequeue()
		sol = append(sol, curr.Val)
		if curr.Left != nil {
			queue.Enqueue(curr.Left)
		}
		if curr.Right != nil {
			queue.Enqueue(curr.Right)
		}
	}
	return sol
}

// Queue is a queue of nodes.
type Queue struct {
	items []*Node
}

// NewQueue returns a new queue of nodes.
func NewQueue() *Queue {
	return &Queue{
		items: make([]*Node, 0),
	}
}

// Enqueue enqueues (adds) a node
// in the end of the queue.
func (q *Queue) Enqueue(node *Node) {
	q.items = append(q.items, node)
}

// Dequeue dequeues (removes) a node
// from the front of the queue.
// If the queue is empty, it returns nil.
func (q *Queue) Dequeue() *Node {
	if q.IsEmpty() {
		return nil
	}
	front := q.Front()
	q.items = q.items[1:]
	return front
}

// Front returns the node in the front
// of the queue.
// If the queue is empty, it returns nil.
func (q *Queue) Front() *Node {
	if q.IsEmpty() {
		return nil
	}
	return q.items[0]
}

// Size returns the number of nodes
// in the queue.
func (q *Queue) Size() int {
	return len(q.items)
}

// IsEmpty returns whether the queue
// has no node (true) or has nodes (false).
func (q *Queue) IsEmpty() bool {
	return q.Size() == 0
}

main.go

package binarytree

import "fmt"

// Here is an example
func main() {
	t := &Tree{
		Root: &Node{
			Val: 1,
			Left: &Node{
				Val: 2,
				Left: &Node{
					Val: 3,
				},
				Right: &Node{
					Val: 4,
				},
			},
			Right: &Node{
				Val: 5,
			},
		},
	}
	fmt.Println(BFSTraversal(t)) // [1 2 5 3 4]
}

In main.go, we built this tree:

And here are the different traversals of this tree:

See "Binary Tree Depth-First Search (DFS) Traversals in Go (GoLang)" HERE.