Last active
July 25, 2023 02:46
-
-
Save maxclav/c05cfe8711a66810dfed9a32d9866eb1 to your computer and use it in GitHub Desktop.
Binary Tree Breadth-First Search (BFS) Zigzag Level Order Traversals in Go (GoLang).
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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]] | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
TODO: Rename the queue to
deque
(Double-ended queue)