I was playing around with implementing Depth First Search (DFS) and Breadth First Search (BFS) in Go today.
I made a tree which looked like this…
0 / \ 1 2 / \ / \ 3 4 5 6 / \ 7 8 I then made some Go code to walk the tree using DFS and BFS:
package main import "fmt" // Node is a very basic struct which represents // a node in the tree. type Node struct { Value int Left *Node Right *Node } // dfs() walks the tree (starting at the provided root node) // in a depth first fashion. It uses a stack. func dfs(node *Node) { // base case if node == nil { return } fmt.Println("DFS visiting:", node.Value) if node.Left != nil { dfs(node.Left) } if node.Right != nil { dfs(node.Right) } } // bfs() walks the tree (starting at the provided root node) // in a breadth first fashion. It uses a queue. func bfs(node *Node) { // base case if node == nil { return } queue := []*Node{node} depth := 0 for len(queue) >= 1 { for _, node := range queue { queue = queue[1:] fmt.Printf("BFS visiting: %d (depth: %d)\n", node.Value, depth) if node.Left != nil { queue = append(queue, node.Left) } if node.Right != nil { queue = append(queue, node.Right) } } depth += 1 } } func main() { // define our tree (see above diagram) tree := &Node{ Value: 0, Left: &Node{ Value: 1, Left: &Node{ Value: 3, }, Right: &Node{ Value: 4, }, }, Right: &Node{ Value: 2, Left: &Node{ Value: 5, }, Right: &Node{ Value: 6, Left: &Node{ Value: 7, }, Right: &Node{ Value: 8, }, }, }, } // call our funcs dfs(tree) bfs(tree) } Running the code outputs:
...