Data Structures: 5. Binary Tree

Apr 10, 2022

programming, go, data-structures, generics

Introduction #

A binary tree is a tree where each node has up to two leaves, and each of those leaves has up to two leaves. So you start with a root node and then fan out, like a genealogical tree.

The way the insertion works is that you look at the root node and decided whether the value you are trying to insert is less than or greater than the root node node value. If less than then you go down the left hand, if more than then the right. You repeat this process for each node in turn. The result is that the tree is automatically sorted, just by insertion. Because you are essentially halving the number of items you need to investigate each time, this is very efficient.

So if we insert the array (12, 4, 16, 0, 8, -2, 2, 6, 10, 14, 18) into a binary tree we would end up with a structure that looks as follows:

flowchart TD; A([12]) --> B([4]) A([12]) --> C([16]) B([4]) --> D([0]) B([4]) --> E([8]) D([0]) --> F([-2]) D([0]) --> G([2]) E([8]) --> H([6]) E([8]) --> I([10]) C([16]) --> J([14]) C([16]) --> K([18])

Solution #

package main

import (
    "fmt"

    "golang.org/x/exp/constraints"
)

type Leaf[T constraints.Ordered] struct {
    data  T
    left  *Leaf[T]
    right *Leaf[T]
}

type BinaryTree[T constraints.Ordered] struct {
    root *Leaf[T]
}

func (bt *BinaryTree[T]) IsEmpty() bool {

    if bt.root == nil {
        return true
    }

    return false
}

func (l *Leaf[T]) search(term T) any {

    if l == nil {
        return nil
    } else if l.data == term {
        return l.data
    } else {
        if l.data > term {
            return l.left.search(term)
        }

        return l.right.search(term)
    }
}

func (bt *BinaryTree[T]) Search(term T) any {

    if bt == nil {
        return nil
    } else {
        return bt.root.search(term)
    }
}

func (l *Leaf[T]) listPreOrderTraverse(data []T) []T {

    if l != nil {
        data = append(data, l.data)
        data = l.left.listPreOrderTraverse(data)
        data = l.right.listPreOrderTraverse(data)
    }

    return data
}

func (l *Leaf[T]) listInOrderTraverse(data []T) []T {

    if l != nil {
        data = l.left.listInOrderTraverse(data)
        data = append(data, l.data)
        data = l.right.listInOrderTraverse(data)
    }

    return data
}

func (l *Leaf[T]) listReverseInOrderTraverse(data []T) []T {

    if l != nil {
        data = l.right.listReverseInOrderTraverse(data)
        data = append(data, l.data)
        data = l.left.listReverseInOrderTraverse(data)
    }

    return data
}

func (l *Leaf[T]) listPostOrderTraverse(data []T) []T {

    if l != nil {
        data = l.left.listPostOrderTraverse(data)
        data = l.right.listPostOrderTraverse(data)
        data = append(data, l.data)
    }

    return data
}

func (bt *BinaryTree[T]) ListPreOrderTraverse() []T {

    var data []T

    if bt == nil {
        return nil
    } else {
        return bt.root.listPreOrderTraverse(data)
    }
}

func (bt *BinaryTree[T]) ListInOrderTraverse() []T {

    var data []T

    if bt == nil {
        return nil
    } else {
        return bt.root.listInOrderTraverse(data)
    }
}

func (bt *BinaryTree[T]) ListReverseInOrderTraverse() []T {

    var data []T

    if bt == nil {
        return nil
    } else {
        return bt.root.listReverseInOrderTraverse(data)
    }
}

func (bt *BinaryTree[T]) ListPostOrderTraverse() []T {

    var data []T

    if bt == nil {
        return nil
    } else {
        return bt.root.listPostOrderTraverse(data)
    }
}

func (l *Leaf[T]) insert(value T) {

    if l == nil {
        return
    } else if value <= l.data {
        if l.left == nil {
            l.left = &Leaf[T]{
                data:  value,
                left:  nil,
                right: nil}
        } else {
            l.left.insert(value)
        }
    } else {
        if l.right == nil {
            l.right = &Leaf[T]{
                data:  value,
                left:  nil,
                right: nil}
        } else {
            l.right.insert(value)
        }
    }
}

func (bt *BinaryTree[T]) Insert(value T) *BinaryTree[T] {

    l := &Leaf[T]{}
    l.data = value
    l.left = nil
    l.right = nil

    if bt.root == nil {
        bt.root = l
    } else {
        bt.root.insert(value)
    }

    return bt
}

func main() {

    fmt.Println("Create a binary for integers...")

    bt := &BinaryTree[int]{}

    if bt.IsEmpty() {
        fmt.Println("Binary tree is empty")
    }

    fmt.Println()
    fmt.Println("Insert some integers (12, 4, 16, 0, 8, -2, 2, 6, 10, 14, 18)")

    bt.Insert(12)
    bt.Insert(4)
    bt.Insert(16)
    bt.Insert(0)
    bt.Insert(8)
    bt.Insert(-2)
    bt.Insert(2)
    bt.Insert(6)
    bt.Insert(10)
    bt.Insert(14)
    bt.Insert(18)

    if !bt.IsEmpty() {
        fmt.Println("Binary tree is not empty")
    }

    fmt.Println()
    fmt.Println("Test the search functionality...")
    fmt.Printf("Should find -2: %v\n", bt.Search(-2))
    fmt.Printf("Should find 12: %v\n", bt.Search(12))
    fmt.Printf("Should find 18: %v\n", bt.Search(18))
    fmt.Printf("Should not find 21: %v\n", bt.Search(21))

    fmt.Println()
    fmt.Println("List preOrderTraverse:")
    fmt.Printf("%+v\n", bt.ListPreOrderTraverse())

    fmt.Println()
    fmt.Println("List inOrderTraverse (ascending):")
    fmt.Printf("%+v\n", bt.ListInOrderTraverse())

    fmt.Println()
    fmt.Println("List reverseInOrderTraverse (descending):")
    fmt.Printf("%+v\n", bt.ListReverseInOrderTraverse())

    fmt.Println()
    fmt.Println("List postOrderTraverse:")
    fmt.Printf("%+v\n", bt.ListPostOrderTraverse())

    fmt.Println()
    fmt.Println("Now create a binary tree for strings...")

    bts := &BinaryTree[string]{}

    if bts.IsEmpty() {
        fmt.Println("Binary tree is empty")
    }

    fmt.Println()
    fmt.Println("Insert some integers (12, 4, 16, 0, 8, -3, 2, 6, 10, 14, 18)")
    fmt.Println("Insert some strings ('Cat','Dog','Mouse','Horse','Pig','Bird','Ant','Rabbit','Cow','Goat','Elephant')")

    bts.Insert("Cat")
    bts.Insert("Dog")
    bts.Insert("Mouse")
    bts.Insert("Horse")
    bts.Insert("Pig")
    bts.Insert("Bird")
    bts.Insert("Ant")
    bts.Insert("Rabbit")
    bts.Insert("Cow")
    bts.Insert("Goat")
    bts.Insert("Elephant")

    if !bts.IsEmpty() {
        fmt.Println("Binary tree is not empty")
    }

    fmt.Println()
    fmt.Println("Test the search functionality...")
    fmt.Printf("Should find 'Mouse': %v\n", bts.Search("Mouse"))
    fmt.Printf("Should find 'Cat': %v\n", bts.Search("Cat"))
    fmt.Printf("Should find 'Elephant': %v\n", bts.Search("Elephant"))
    fmt.Printf("Should not find 'Unicorn': %v\n", bts.Search("Unicorn"))

    fmt.Println()
    fmt.Println("List preOrderTraverse:")
    fmt.Printf("%+v\n", bts.ListPreOrderTraverse())

    fmt.Println()
    fmt.Println("List inOrderTraverse (ascending):")
    fmt.Printf("%+v\n", bts.ListInOrderTraverse())

    fmt.Println()
    fmt.Println("List reverseInOrderTraverse (descending):")
    fmt.Printf("%+v\n", bts.ListReverseInOrderTraverse())

    fmt.Println()
    fmt.Println("List postOrderTraverse:")
    fmt.Printf("%+v\n", bts.ListPostOrderTraverse())
}

Testing #

Create a binary for integers...
Binary tree is empty

Insert some integers (12, 4, 16, 0, 8, -2, 2, 6, 10, 14, 18)
Binary tree is not empty

Test the search functionality...
Should find -2: -2
Should find 12: 12
Should find 18: 18
Should not find 21: <nil>

List preOrderTraverse:
[12 4 0 -2 2 8 6 10 16 14 18]

List inOrderTraverse (ascending):
[-2 0 2 4 6 8 10 12 14 16 18]

List reverseInOrderTraverse (descending):
[18 16 14 12 10 8 6 4 2 0 -2]

List postOrderTraverse:
[-2 2 0 6 10 8 4 14 18 16 12]

Now create a binary tree for strings...
Binary tree is empty

Insert some integers (12, 4, 16, 0, 8, -3, 2, 6, 10, 14, 18)
Insert some strings ('Cat','Dog','Mouse','Horse','Pig','Bird','Ant','Rabbit','Cow','Goat','Elephant')
Binary tree is not empty

Test the search functionality...
Should find 'Mouse': Mouse
Should find 'Cat': Cat
Should find 'Elephant': Elephant
Should not find 'Unicorn': <nil>

List preOrderTraverse:
[Cat Bird Ant Dog Cow Mouse Horse Goat Elephant Pig Rabbit]

List inOrderTraverse (ascending):
[Ant Bird Cat Cow Dog Elephant Goat Horse Mouse Pig Rabbit]

List reverseInOrderTraverse (descending):
[Rabbit Pig Mouse Horse Goat Elephant Dog Cow Cat Bird Ant]

List postOrderTraverse:
[Ant Bird Cow Elephant Goat Horse Rabbit Pig Mouse Dog Cat]