As an exercise in using channels in Go I implemented a breadth-first traversal of a binary tree, using a channel as a queue to store the order of the nodes to traverse. After ironing out a bunch of bugs related to all goroutines sleeping I ended up with this code:
package main
import "fmt"
type Node struct {
Value int
Left *Node
Right *Node
}
var tree *Node
func init() {
tree = &Node{1, &Node{2, &Node{4, &Node{6, nil, nil}, nil}, &Node{5, nil, &Node{7, nil, nil}}}, &Node{3, nil, nil}}
}
func (t *Node) BFS() {
c := make(chan *Node, 512)
c <- t
bfs(c)
close(c)
}
func bfs(c chan *Node) {
empty := false
for {
select {
case next := <-c:
if next != nil {
c <- next.Left
c <- next.Right
fmt.Println(next.Value)
}
default:
empty = true
}
if empty {
break
}
}
}
func main() {
tree.BFS()
}
While I appreciate advice on any part of the code, I am specifically concerned about the tight for
loop in the body of bfs()
, the not particularly safe-for-concurrency code and other possible issues mentioned in this question on stackoverflow.