DEV Community

Cover image for Data Structures and Algorithms with Go (2): Growing Your Go Skills with Trees
MacBobby Chibuzor
MacBobby Chibuzor

Posted on

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
}
Enter fullscreen mode Exit fullscreen mode

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)
}
Enter fullscreen mode Exit fullscreen mode

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.

Top comments (0)