Trees in Go

A graph is a finite and nonempty set of vertices and edges. A directed graph is a graph whose edges have a direction associated with them. A directed acyclic graph is a directed graph with no cycles in it. A tree is a directed acyclic graph that satisfies three more principles: firstly, it has a root node: the entry point to the tree; secondly, every vertex, except the root, has one and only one entry point; and thirdly, there is a path that connects the root with each vertex and belongs to the tree.

As a result, the root is the first node of the tree. Each node can be connected to one or more nodes depending on the tree type. If each node leads to one and only one other node, then the tree is a linked list!

The most commonly used type of tree is called a binary tree because each node can have up to two children. The following figure shows a graphical representation of a binary tree's data structure:

The presented code will only show you how to create a binary tree and how to traverse it in order to print all of its elements as proof that Go can be used for creating a tree data structure. Therefore, it will not implement the full functionality of a binary tree, which also includes deleting a tree node and balancing a tree.

The code of tree.go will be presented in three parts.

The first part is the expected preamble as well as the definition of the node, as given here:

package main 
 
import ( 
   "fmt" 
   "math/rand" 
   "time" 
) 
type Tree struct { 
   Left  *Tree 
   Value int 
   Right *Tree 
} 

The second part contains functions that allow you to traverse a tree in order to print all of its elements, create a tree with randomly generated numbers, and insert a node into it:

func traverse(t *Tree) { 
   if t == nil { 
         return 
   } 
   traverse(t.Left) 
   fmt.Print(t.Value, " ") 
   traverse(t.Right) 
} 
 
func create(n int) *Tree { 
   var t *Tree 
   rand.Seed(time.Now().Unix()) 
   for i := 0; i< 2*n; i++ { 
         temp := rand.Intn(n) 
         t = insert(t, temp) 
   } 
   return t 
} 
 
func insert(t *Tree, v int) *Tree { 
   if t == nil { 
         return&Tree{nil, v, nil} 
   } 
   if v == t.Value { 
         return t 
   } 
   if v <t.Value { 
         t.Left = insert(t.Left, v) 
         return t 
   } 
   t.Right = insert(t.Right, v) 
   return t 
} 

The second if statement of insert() checks whether a value already exists in the tree, in order to not add it again. The third if statement identifies whether the new element will be on the left or right-hand side of the current node.

The last part is the implementation of the main() function:

func main() { 
   tree := create(30) 
   traverse(tree) 
   fmt.Println() 
   fmt.Println("The value of the root of the tree is", tree.Value) 
} 

Executing tree.go will generate the following output:

$ go run tree.go
0 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 21 22 23 24 25 26 27 28 29
The value of the root of the tree is 16