Last active
July 22, 2023 19:38
-
-
Save maxclav/696e39e15bd319293d6c3676a0b60f7d to your computer and use it in GitHub Desktop.
Binary Tree Breadth-First Search (BFS) Traversal using a queue 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 | |
} | |
// 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 | |
} |
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(BFSTraversal(t)) // [1 2 5 3 4] | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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.