Data Structures and Algorithms with Go (2): Growing Your Go Skills with Trees

Trees

Trees are non-linear data structures used mainly for searching. Trees have maximum nodes of two children and a minimum of none. In trees, the property values of the left node are lesser than the property values of the right node. Nodes with no children are considered leaves.

Must-knows about trees

1. A binary tree is a data structure where each node has 0, 1, or 2 sub-nodes.
2. The root node is the first node of the tree, having no parents.
3. An edge is the link from child to parent.
4. The depth/height of the tree is the longest path from the root node to the furthest node.
5. The depth of a node is the number of edges from the node to the root of the tree.
6. A leaf is a node with no children.
7. The children of the same parent are called siblings.
8. Ancestors of a node are parent/grandparents to the parent of the node's parent.
9. Trees are either balanced or unbalanced and balancing a tree is difficult and slow.
10. The size of a tree is the number of descendants it has including itself.

Binary search tree

A tree is called a binary tree if it has a maximum of two child nodes. An empty tree is also a valid binary tree. Binary trees have a root node with a left and a right subtree. Binary search trees allow look-up operations, as well as addition, and removal of elements. They store keys in a sorted order, to make look-up operations faster. Their space complexity is of the order O(n), but their operations like insert, search, and delete are of the order O(log n). Binary trees have the following properties:

• key of type int
• value of type int
• LeftNode of the node's type instance
• RightNode of the node's type instance

For example, the properties are arranged thus:

type TreeNode struct {
    key int
    value int
    leftNode *TreeNode // best to put it first, as the orientation is left | value | right
    rightNode *TreeNode
}

Binary tree operations

Operations possible with binary trees are grouped into two:

Basic Operations

• Inserting elements to a tree
• Deleting elements from a tree
• Searching for elements in a tree
• Traversing the tree

Auxiliary Operations

• Finding the size of a tree
• Finding the height of a tree
• Finding the level with the maximum sum
• Finding the least common ancestor (LCA) for a particular pair of nodes
• Others

Applications of binary trees

The following are examples of use-cases of binary trees:

• Expression trees for compilers
• Huffman coding trees for data compression algorithms
• Binary search trees (BST) for searching, inserting, and deleting in O(log n)
• Priority queues (PQ) for searching and deleting minimum or maximum values in O(log n) time.

Implementing binary trees in Go

Below is an example code where binary trees are implemented:

package main

import (
    "fmt"
    "math/rand"
    "time"
)

// Tree type of recursive struct
type Tree struct {
    Left  *Tree
    Value int
    Right *Tree
}

// traverse method allows visiting of nodes with recursion
func traverse(t *Tree) {
    if t == nil {
        return
    }
    traverse(t.Left)
    fmt.Print(t.Value, " ")
    traverse(t.Right)
}

// create function populates the branches with random integers
func create(n int) *Tree {
    var t *Tree
    rand.Seed(time.Now().Unix())
    for i := 0; i < 2*n; i++ {
        temp := rand.Intn(n * 2)
        t = insert(t, temp)
    }
    return t
}

// insert recursive function does lots of functions with each if statements
func insert(t *Tree, v int) *Tree {
    if t == nil { // if the tree is empty
        return &Tree{nil, v, nil}
    }
    if v == t.Value { // if the value exists in the tree
        return t
    }
    if v < t.Value { // if the value should go left or right
        t.Left = insert(t.Left, v)
    }
    t.Right = insert(t.Right, v)
    return t
}

// main function
func main() {
    tree := create(10)
    fmt.Println("The root of the tree is ", tree.Value, " \n.")
    traverse(tree)
    // fmt.Println()
    tree = insert(tree, -10)
    tree = insert(tree, -2)
    traverse(tree)
    // fmt.Println()
    fmt.Println(" \n The root of the tree is ", tree.Value)
}

Conclusion

This article teaches the reader about Trees and binary trees. The possible operations with binary trees were also given, along with an implementation of some of these operations. In a future article, applications of binary trees in problem-solving with the Go programming languages will be given.