Playing around with trees in Golang

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:

$ go run main.go
DFS visiting: 0             # start DFS
DFS visiting: 1
DFS visiting: 3
DFS visiting: 4
DFS visiting: 2
DFS visiting: 5
DFS visiting: 6
DFS visiting: 7
DFS visiting: 8
BFS visiting: 0 (depth: 0)  # start BFS
BFS visiting: 1 (depth: 1)
BFS visiting: 2 (depth: 1)
BFS visiting: 3 (depth: 2)
BFS visiting: 4 (depth: 2)
BFS visiting: 5 (depth: 2)
BFS visiting: 6 (depth: 2)
BFS visiting: 7 (depth: 3)
BFS visiting: 8 (depth: 3)

Takeaways

Important takeaways from this:

DFS uses a stack. Recursion is typically the best choice.
BFS uses a queue. Don’t use recursion; use iteration (on the queue).

Takeaways#

Takeaways