2 Different Ways to Implement BFS in Golang
Breadth-first search is an algorithm we frequently use to traverse trees. Before we jump right into implementing it, let’s do a quick recap on bfs.
Recap: What is Breadth-First Search?
For the purpose of illustration, let’s imagine we have a perfect binary tree, where a perfect binary tree is a binary tree with all leaf nodes at the same depth and all internal nodes have degree 2(NIST). Assume we want to do a bfs traversal of the tree while keeping track of the level of the node.
A BFS traversal of the above tree would look like this: [1, 2, 3, 4, 5, 6, 7]. Notice a pattern in the visit sequence - in bfs we begin by visiting the root node first, before moving downwards to visit all the nodes in the next adjacent row, in a left-to-right fashion. That’s all there is to it really, nothing complicated.
Now that we have gotten the gist of it, take 30 seconds to think about how we could implement this algorithm in code before scrolling to some suggested implementations.
Disclaimer: the following code examples will be presented in Golang, but as with programming languages, they can be “translated” to the programming language of your choice. What’s more important to take away from this article is the concept of using different data structures to solve the same problem and the thought process behind it.
2 different ways we can implement BFS(in Golang)
Now that we understand what is a bfs traversal, let us explore 2 different ways we can implement the BFS algorithm. The following 2 methods of implementation mainly differ in the data structures being used.
1. Using a queue data structure
Given a node, we can implement NodeWithLevel struct as a data structure to store 2 things: 1. the node and 2. its corresponding node level.
/**
* Definition for a Node.
* type Node struct {
* Val int
* Left *Node
* Right *Node
* Next *Node
* }
*/type NodeWithLevel struct{
node *Node
level int
}
Then, with the help of a Golang array, we can use it to implement a queue system to store our NodeWithLevel structs.
q := []NodeWithLevel{
{
node: root,
level: 0,
},
}Now comes the algorithm. First, we begin to push the root node into the queue. Then we execute the following steps:
- Dequeue the root node from the front queue(fifo) — indicates that we have visited it.
- If the queue has a left child, it means it also has a right child(since it’s a perfect binary tree). In such a scenario, we will queue both left and right child to the back of the queue(fifo). Otherwise, we simply skip this step.
- Repeat the above 2 steps until the queue is empty.
Notice by executing the steps above with the help of a queue, we are traversing the binary tree in a BFS fashion. Let’s illustrate it with the above example:
We begin with visited = [] and queue = [1].
iteration 1.1: After dequeuing node 1 from the queue, we mark the the node as “visited”.
iteration 1.2: We add its left and right child to the back of the queue.
At the end of iteration 1, we have visited = [1], queue = [2, 3]; following iterations would look like this:
iteration 2.1: visited =[1, 2], queue = [3]
iteration 2.2: visited =[1, 2], queue = [3, 4, 5]
— — — — — — — — — — — — — — — — — — — — —
iteration 3.1: visited =[1, 2, 3], queue = [4, 5]
iteration 3.2: visited =[1, 2, 3], queue = [4, 5, 6, 7]
— — — — — — — — — — — — — — — — — — — — —
iteration 4.1: visited =[1, 2, 3, 4], queue = [5, 6, 7]
iteration 4.2: visited =[1, 2, 3, 4], queue = [5, 6, 7]
— — — — — — — — — — — — — — — — — — — — —
iteration 5.1: visited =[1, 2, 3, 4, 5], queue = [6, 7]
iteration 5.2: visited =[1, 2, 3, 4, 5], queue = [6, 7]
— — — — — — — — — — — — — — — — — — — — —
iteration 6.1: visited =[1, 2, 3, 4, 5, 6], queue = [7]
iteration 6.2: visited =[1, 2, 3, 4, 5, 6], queue = [7]
— — — — — — — — — — — — — — — — — — — — —
iteration 7.1: visited =[1, 2, 3, 4, 5, 6, 7], queue = []
iteration 7.2: visited =[1, 2, 3, 4, 5, 6, 7], queue = []
— — — — — — — — — — — — — — — — — — — — —
This is how the overall code would look like:
/**
* Definition for a Node.
* type Node struct {
* Val int
* Left *Node
* Right *Node
* Next *Node
* }
*/type NodeWithLevel struct{
node *Node
level int
}func bfs(root *Node) *Node {
if root == nil{ //to handle edge case
return root
}
q := []NodeWithLevel{
{
node: root,
level: 0,
},
}
visited := []*Node{}for len(q) > 0{
vertex := q[0]
node, level := vertex.node, vertex.level
visited = append(visited, node)
q = q[1:] //dequeue first node in queue(fifo)
if node.Left != nil{ //have both left and right since it's a perfect binary tree
leftNode := NodeWithLevel{
node: node.Left,
level: level+1,
}
q = append(q, leftNode) //append left-child to back of queue(fifo)
rightNode := NodeWithLevel{
node: node.Right,
level: level+1,
}
q = append(q, rightNode) //append right-child to back of queue(fifo)
}
}
return root
}
The space complexity of this implementation is O(n). One way we could further optimize the speed of this piece of suggested code is that instead of dequeuing the node and then appending to another visit array, we could use an O(1) pointer to keep track of the last visited node in the queue. This will eliminate the need to dequeue while allowing us to keep track of the upcoming node to be visited. We also can know for sure that the nodes before and including the pointer position are the visited nodes that are already ordered in the visited sequence.
2. Using a hash map
By using a hash map, we could store the node level as keys and the array containing all nodes in that particular node level from left to right as an array.
hashMap[0] = []*Node{root}
for{ // traverse row by row
nodeArr, ok := hashMap[i]
if !ok{
break
}
for j, node := range nodeArr{ //traverse every node in row i
visited = append(visited, node)
if node.Left != nil{ //have both children since it's perfect BT
_, ok := hashMap[i+1] //check if hashmap key exists
if !ok{ //if hashmap key does not exist, add empty arr as value
hashMap[i+1] = []*Node{}
}
hashMap[i+1] = append(hashMap[i+1], node.Left)
hashMap[i+1] = append(hashMap[i+1], node.Right)
}
}
i += 1
}As illustrated by the code snippet above, we traverse through every level by beginning key number 0(node level 0) and increment by 1 each time we finish traversing through the lateral nodes on the same row. Also notice that when we have finished traversing through all nodes on node level x, we can also deduce that we have also added all nodes on level x+1 to the key x+1. For comprehensiveness, let’s do a break down on how the hash map and the visited array would like on every iteration:
iteration 0: visited = [], hashmap = {0:[1]}
iteration 1: visited = [1], hashmap = {0:[1], 1:[2, 3]}
iteration 2: visited = [1, 2], hashmap = {0:[1], 1:[2, 3], 2:[4, 5]}
iteration 3: visited = [1, 2, 3], hashmap = {0:[1], 1:[2, 3], 2:[4, 5, 6, 7]}
iteration 4: visited = [1, 2, 3, 4], hashmap = {0:[1], 1:[2, 3], 2:[4, 5, 6, 7]}
iteration 5: visited = [1, 2, 3, 4, 5], hashmap = {0:[1], 1:[2, 3], 2:[4, 5, 6, 7]}
iteration 6: visited = [1, 2, 3, 4, 5, 6], hashmap = {0:[1], 1:[2, 3], 2:[4, 5, 6, 7]}
iteration 7: visited = [1, 2, 3, 4, 5, 6, 7], hashmap = {0:[1], 1:[2, 3], 2:[4, 5, 6, 7]}
The full code snippet would look something like this:
/**
* Definition for a Node.
* type Node struct {
* Val int
* Left *Node
* Right *Node
* Next *Node
* }
*/func bfs(root *Node) *Node {
if root == nil{
return root
}
hashMap := make(map[int][]*Node)
hashMap[0] = []*Node{root}
visited := []*Node{}
i := 0
for{ // traverse row by row
nodeArr, ok := hashMap[i]
if !ok{
break
}
for j, node := range nodeArr{ //traverse every node in row i
visited = append(visited, node)
if node.Left != nil{ //have both children since it's perfect BT
_, ok := hashMap[i+1] //check if hashmap key exists
if !ok{ //if hashmap key does not exist, add empty arr as value
hashMap[i+1] = []*Node{}
}
hashMap[i+1] = append(hashMap[i+1], node.Left)
hashMap[i+1] = append(hashMap[i+1], node.Right)
}
}
i += 1
}
return root
}
As seen in the above implementation, space complexity is also O(n), where the total size of hash map and the visited array share a linear relationship with the number of nodes in the tree. We could also further optimise the amount of space by deleting the key-value pair once we are done visiting the nodes in the row.
And that’s it, I hope this short write-up helped you understand bfs implementation in Golang better, or perhaps discover a different implementation. If this write-up helped and you would like more of such articles about data structures/algorithms implementations using Golang, do leave a clap, comment or follow me for more of such posts! Thanks for reading!
P.s. I welcome all feedback and suggestions! Whether is it a code optimization suggestion or a bug report, leave a comment! I‘m more than happy to learn from the community, cheers!
Join FAUN: Website 💻|Podcast 🎙️|Twitter 🐦|Facebook 👥|Instagram 📷|Facebook Group 🗣️|Linkedin Group 💬| Slack 📱|Cloud Native News 📰|More.
If this post was helpful, please click the clap 👏 button below a few times to show your support for the author 👇
