Binary Tree Breadth-First Search (BFS) Level Order Traversals in Go (GoLang).

binarytree-traversals-bfs-levelorder.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
}

// LevelOrder uses Breadth-First Search (BFS) with queues
// to return the Level Order traversal of the tree nodes.
func LevelOrder(t *Tree) [][]int {
	sol := make([][]int, 0)
	if t == nil || t.Root == nil {
		return sol
	}
	
	root := t.Root

	sol = append(sol, []int{root.Val})

	queue := NewQueue()
	queue.Enqueue(root)

	for !queue.IsEmpty() {
		level := queue.Size()
		vals := make([]int, 0)
		for i := 0; i < level; i++ {
			current := queue.Dequeue()
			childrenVals := current.ChildrenVals()
			vals = append(vals, childrenVals...)
			queue.EnqueueChildren(current)
		}
		if len(vals) != 0 {
			sol = append(sol, vals)
		}
	}

	return sol
}

// ChildrenVals returns the children values in a slice.
func (n *Node) ChildrenVals() []int {
	vals := make([]int, 0, 2)
	if n.Left != nil {
		vals = append(vals, n.Left.Val)
	}
	if n.Right != nil {
		vals = append(vals, n.Right.Val)
	}
	return vals
}

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

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

// Enqueue enqueues the Node `node` in the Queue.
func (q *Queue) Enqueue(node *Node) {
	q.items = append(q.items, node)
}

// EnqueueChildren enqueues the children
// of Node `node` in the queue.
func (q *Queue) EnqueueChildren(node *Node) {
	if node.Left != nil {
		q.Enqueue(node.Left)
	}
	if node.Right != nil {
		q.Enqueue(node.Right)
	}
}

// Dequeue dequenes the first Node `node`
// from the queue and returns it.
// It returns nil if the queue is empty.
func (q *Queue) Dequeue() *Node {
	if q.IsEmpty() {
		return nil
	}
	node := q.items[0]
	q.items = q.items[1:]
	return node
}

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

// IsEmpty returns whether
// the Queue is empty (true) or not (false).
func (q *Queue) IsEmpty() bool {
	return q.Size() == 0
}

func (q *Queue) Println() {
	var sb strings.Builder
	sb.WriteString("[")
	if !q.IsEmpty() {
		for _, item := range q.items[:q.Size()-1] {
			sb.WriteString(fmt.Sprintf("%v ", item.Val))
		}
		sb.WriteString(fmt.Sprintf("%v", q.items[q.Size()-1].Val))
	}
	sb.WriteString("]")
	fmt.Println(sb.String())
}

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(LevelOrder(t)) // [[1] [2 5] [3 4]]
}