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

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

// ZigzagLevelOrder uses Breadth-First Search (BFS) with queues
// to return the Zigzag Level Order traversal of the tree nodes.
func ZigzagLevelOrder(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 := NewQueueNodes()
	queue.Enqueue(root)
	var isReverse bool = false

	for !queue.IsEmpty() {
		levelSize := queue.Size()
		levelQueue := NewQueueInts(isReverse)
		for i := 0; i < levelSize; i++ {
			node := queue.Dequeue()
			queue.EnqueueChildren(node)
			levelQueue.EnqueueChildrenValues(node)
		}
		isReverse = !isReverse
		if !levelQueue.IsEmpty() {
			sol = append(sol, levelQueue.Values())
		}
	}

	return sol
}

/* Queue of ints */

type QueueInts struct {
	items     []int
	isReverse bool
}

func NewQueueInts(isReverse bool) *QueueInts {
	return &QueueInts{
		items:     make([]int, 0),
		isReverse: isReverse,
	}
}

func (q *QueueInts) EnqueueChildrenValues(node *Node) {
	if q.isReverse {
		if node.Left != nil {
			q.EnqueueBack(node.Left.Val)
		}
		if node.Right != nil {
			q.EnqueueBack(node.Right.Val)
		}
	} else {
		if node.Left != nil {
			q.EnqueueFront(node.Left.Val)
		}
		if node.Right != nil {
			q.EnqueueFront(node.Right.Val)
		}
	}
}

func (q *QueueInts) EnqueueFront(val int) {
	q.items = append([]int{val}, q.items...)
}

func (q *QueueInts) EnqueueBack(val int) {
	q.Enqueue(val)
}

func (q *QueueInts) Enqueue(val int) {
	q.items = append(q.items, val)
}

func (q *QueueInts) Dequeue() int {
	if q.IsEmpty() {
		return -1
	}
	val := q.items[0]
	q.items = q.items[1:]
	return val
}

func (q *QueueInts) Size() int {
	return len(q.items)
}

func (q *QueueInts) IsEmpty() bool {
	return q.Size() == 0
}

func (q *QueueInts) Values() []int {
	res := make([]int, q.Size())
	copy(res, q.items)
	return res
}

/* Queue of Nodes */

type QueueNodes struct {
	items []*Node
}

func NewQueueNodes() *QueueNodes {
	return &QueueNodes{
		items: make([]*Node, 0),
	}
}

func (q *QueueNodes) Enqueue(n *Node) {
	q.items = append(q.items, n)
}

func (q *QueueNodes) EnqueueChildren(n *Node) {
	if n.Left != nil {
		q.Enqueue(n.Left)
	}
	if n.Right != nil {
		q.Enqueue(n.Right)
	}
}

func (q *QueueNodes) Dequeue() *Node {
	if q.IsEmpty() {
		return nil
	}
	n := q.items[0]
	q.items = q.items[1:]
	return n
}

func (q *QueueNodes) Size() int {
	return len(q.items)
}

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

TODO: Rename the queue to deque (Double-ended queue)