A Binary Tree in Go

Most of the implementations that I've seen online are restricted to only one type. As a refresher I've followed suit and implemented a basic binary tree which works with integers. Next week's post will be on a polymorphic binary tree.

The entire code is in a single file, methods, driver, and all. Notes will be made in the last section of this post instead of explaining everything in detail. If you're new to binary trees, view the wiki page.

You can view my Go implementation on Github or see it in action on the Go Playground.

Anyways, here's my take at a polymorphic tree:

Have an interface which specifies methods that abstract the core parts of a node - Left, Right, Data, Comparison Function, etc. This way the struct that represents a node can have more fields than two pointers and one data variable - all the binary tree package functions care about are:

  • being able to 'get' and 'set' the left and right children along with other important fields
  • a comparison function so that it can traverse the tree correctly in finding, inserting, and deleting nodes

Unlike this week's version, the polymorphic binary tree will be created as a package.

Notes

  • I'm heading back to school within two weeks to finish off my Senior year, woohoo! Unfortunately that means there's less time to work on all things Go. Instead of releasing weekly posts that may not be of much value, I'll be releasing material as soon as any are ready.

  • Started working on a tool to simplify my workflow. I can't begin to describe how rewarding it is to create a tool that solves a personal problem. I hate that I didn't do it earlier, but I'm glad I started to with Go. Going to develop it more and will release a post on it later.

  • Other Go related projects are in the works...

Notes on the Code

Basic operations:

  • Insert(newValue interface{}) error - Traverses the tree along a route determined by whether the value to be inserted is greater, less than, or equal to the current node's value. Before traversing to a node by invoking the Insert() method on the left or right child, the particular field is checked to see if its value is nil. If so, allocate space for a new node and assign the left/right child to point to it, then copy the new integer to be inserted into the new node's Data field. While an error is returned, there is currently no functionality which checks for any errors.

  • Find(value interface{}) *Node - Traverses tree in search of a Node's Data field that matches the value argument. Upon success the address of the node is returned, nil is returned otherwise.

  • Delete(value interface{}) *Node - Recursive method which deletes most nodes by removing pointer references to them. The single use case where this won't happen is with the root node. Removing a root node will simply set its Data field to nil. In this case such a node is considered empty.

  • Height() int - Recursive method that returns 1 + the maximum value of a call to Height for each of the node's children. If the node is considered empty, 0 is returned. So each node is given a value of 1, and the height is the sum of the tallest 'node trail'.

  • FindMin() int - Recursive method which returns the smallest integer among the left children of a tree.

  • FindMax() int - Recursive method which returns the largest value among the right children of a tree.

  • Print() - Prints the value of each node, traversing the tree in a preorder fashion.

  • min(num1 int, num2 int) int and max(num1 int, num2 int) int - behaves as expected. Naming was kept lowercase to conform to package naming conventions where lowercase functions are not exported. In this case, the practice describes helper functions.


  • Since a struct cannot be nil, there needs to be some way to determine whether a struct is 'empty'. The data field which stores integers is an empty interface. Since an empty interface can in fact be nil, that's what I checked for.

  • Didnt realize that there were so many different ways Delete() could be written. I made sure to write mine on my own version before observing others. Creating algorithms off the top of my head was fun but time consuming.