DEV Community

Cover image for Data Structures in Go: Tree (BST)
Dorin
Dorin

Posted on • Originally published at fodor.org

10 5

Data Structures in Go: Tree (BST)

Introduction

A Tree is a non-linear data structure which consists of one or more nodes where a node can have zero or more references to other nodes which will form a sub-tree.

Alt Text

There are multiple types of trees: ordered, un-ordered, balanced, non-balanced, with two children, with more than two children, etc.

For the purpose of this article I have chosen to implement a non-balanced Binary Search Tree, which is an ordered tree with two child nodes. The one on the left will always contain a smaller value and the one on the right a greater value.

Implementation

To start with, we are going to create a struct which is going to represent a single node of our tree. There will always be a node at the top, to which everything else is going to be added.

// Node : represents a single node of a Tree data structure
type Node struct {
    Left  *Node
    Right *Node
    Data  int
}
Enter fullscreen mode Exit fullscreen mode

Next we add a constructor function New which will take the value of the first node and return an instance of a tree node.

// New : constructor function for a Tree node
func New(data int) *Node {
    return &Node{
        Left:  nil,
        Right: nil,
        Data:  data,
    }
}
Enter fullscreen mode Exit fullscreen mode

Now we are going to add a few methods to our tree node struct. These are going to be: Insert, Contains and Traverse.

The Insert method is going to add a node with the value passed to it, to the tree. We are going to recursively look into all the nodes until we find a suitable location with a nil reference where we can append the new node.

// Insert : adds a node to the tree
func (t *Node) Insert(data int) *Node {
    if data < t.Data {
        if t.Left != nil {
            t.Left.Insert(data)
        } else {
            t.Left = New(data)
        }
    } else {
        if t.Right != nil {
            t.Right.Insert(data)
        } else {
            t.Right = New(data)
        }
    }
    return t
}
Enter fullscreen mode Exit fullscreen mode

Then we add the Contains method which is going to start traversing the tree and look for a node with a specific value. It will return a boolean with the success status.

// Contains : checks if the tree contains a node with a given value
func (t *Node) Contains(data int) bool {
    if t.Data == data {
        return true
    }
    if data < t.Data {
        if t.Left != nil {
            t.Left.Contains(data)
        } else {
            return false
        }
    } else {
        if t.Right != nil {
            t.Right.Contains(data)
        } else {
            return false
        }
    }
    return false
}
Enter fullscreen mode Exit fullscreen mode

And lastly we add the Traverse method which is going to traverse the entirety of the tree and print all its values to the standard output.

// Traverse : prints all elements of the tree
func (t *Node) Traverse() {
    if t.Left != nil {
        t.Left.Traverse()
    }
    fmt.Println(t.Data)
    if t.Right != nil {
        t.Right.Traverse()
    }
}
Enter fullscreen mode Exit fullscreen mode

Conclusion

We ended up with a basic Binary Search Tree which will let us add any element to it with a complexity of O(n) and search, in the worst case also with O(n). This is not ideal and it is possible to improve the tree by making sure it is balanced. A balanced tree would let us search at O(log(n)).

Stay tuned for new posts on how to balance our tree!

Source code with tests

GitHub logo dorin131 / go-data-structures

A collection of data structures implemented in Go

Video

Image of Datadog

Create and maintain end-to-end frontend tests

Learn best practices on creating frontend tests, testing on-premise apps, integrating tests into your CI/CD pipeline, and using Datadog’s testing tunnel.

Download The Guide

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Dive into an ocean of knowledge with this thought-provoking post, revered deeply within the supportive DEV Community. Developers of all levels are welcome to join and enhance our collective intelligence.

Saying a simple "thank you" can brighten someone's day. Share your gratitude in the comments below!

On DEV, sharing ideas eases our path and fortifies our community connections. Found this helpful? Sending a quick thanks to the author can be profoundly valued.

Okay