Binary Trees In Golang
Binary trees are a fairly simple data structure where you have a node that contains some data, and a max of two child nodes that also contain some data, like this:
1
/ \
2 3
Each child node can also have up to two child nodes, and it can grow to as large as is neccessary. Here's one with three levels of nodes.
1
/ \
2 3
/ \ / \
4 5 6 7
Each node can have 0, 1, or two child nodes so this is also a valid binary tree:
1
/ \
2 3
/
4
Binary Trees (or trees with any number of children) are generally used whenever theirs some heirarchical order to the data, or when splitting it up based on certain criterea can speed up searches, for example in Binary Search Trees. In machine learning, Decision trees are another example since they let you follow a path based on true or false questions about the data.
Let's see how to construct and walk through Binary Trees in Go. The first thing we'll do is create a structure that will hold the data, pointers to the left and right children, and a mutex.
type BinaryTree struct {
Data int
Left *BinaryTree
Right *BinaryTree
mu sync.Mutex
}
Now that we have a struct for our binary trees, we can see that inserting data into one is really straightforward because all we have to do is create another 'child' binary tree and assign it's pointer to one of the parent's left or right values. Let's create an Insert method that does this.
func (bt *BinaryTree) Insert(data int, dir rune) {
bt.mu.Lock()
defer bt.mu.Unlock()
node := &BinaryTree{
Data: data,
}
if dir == 'l' {
bt.Left = node
} else {
bt.Right = node
}
return
}
Again, all it does it take the data and which side of the sub-tree you want to insert the child node on and sets it. It doesn't do any checking to see if the node is already set or not, but if you wanted to, of course you could add some logic for that. For example, if you just wanted to insert some data at the "next available" spot in the tree, you could do that. As a matter of fact, a Binary Search Tree kinda handles that natively, and I'll show an example of that later in this post. But for now, let's keep it simple
So let's say, for example we've built our tree by inserting numbers 1 through 7 in each node, like this:
var bt BinaryTree = *CreateBinaryTree(1)
bt.Insert(2, 'l')
bt.Insert(3, 'r')
bt.Left.Insert(4, 'l')
bt.Left.Insert(5, 'r')
bt.Right.Insert(6, 'l')
bt.Right.Insert(7, 'r')
This will give us a binary tree that looks like this:
1
/ \
2 3
/ \ / \
4 5 6 7
Now, we know how to build a tree, next let's see a few different ways we can 'step through' one.
Traversing The Tree
There are a few algorithms we can use to traverse, or 'step through' the tree. Let's look at a few of the recursive ones. Recursion works well here because each sub tree is technically a full tree in itself, so we can just keep calling the travesal method on each sub-tree in the overall tree until there are no more sub-trees left. The main ways to do this are Pre Order, Post Order, and In Order traversal. Let's look at some examples of those algorithms using print statements to visualize which order the tree nodes are processed in.
In all of these algorithms, the base case is that the sub-tree is nil, so we'll keep adding on stack frames until that happens. When that last stack frame returns, the previous stack frame can pick up where it left off before it got pushed under that other stack frame. Each one of these traversal algorithms is an example of Depth First Search. This is because they use a stack (partcicularly the call stack because of the recursion) to 'stack up' nodes to be processed. Using a stack means neighbor nodes are "stuck" under each level of the call stack until their subsequent calls return, so the traversal will continue in one direction prioritizing depth. You could also traverse the tree using queues, which would be give you Breadth First Search. This is because each neighbor node is queued up to get visited next as soon as it's neighbor has been visited.
Pre Order
In Pre Order, it follows one direction printing all the way down until you hit the base case (node is null), then as each stack frame of the first direction returns, it calls the method recursively on the other direction, printing each of those node's data all the way back up until you return from the root call.
func (bt *BinaryTree) PreOrder() {
if bt != nil {
fmt.Printf("%d, ", bt.Data)
bt.Left.PreOrder()
bt.Right.PreOrder()
}
}
1
/ \
2 3
/ \ / \
4 5 6 7
Pre Order traversal on the above tree would give us this print order:
1 2 4 5 3 6 7
Post Order
In this one, it follows one direction all the way down, but doesn't print anything until you meet the base case (hits a null node), then prints the node from the last stack frame before that happened, then hits each neighbor node of that one and prints it while on it's way back down the call stack. As the visits to the neighbor nodes are popped off the call stack, the last direction queued up before that finally gets to execute and this continues until all base cases have been met.
func (bt *BinaryTree) PostOrder() {
if bt != nil {
bt.Left.PostOrder()
bt.Right.PostOrder()
fmt.Printf("%d, ", bt.Data)
}
}
1
/ \
2 3
/ \ / \
4 5 6 7
Printing with Post Order traversal:
4 5 2 6 7 3 1
In Order
In this one, we follow one direction all the way down until you hit the base case then print the first node with no sub-tree, then print it's parent, then print it's sibling. Once the call to print that child returns, those stack frames have popped off so you can print that parent's parent, then follow it's other child and continue the process.
func (bt *BinaryTree) InOrder() {
if bt != nil {
bt.Left.InOrder()
fmt.Printf("%d, ", bt.Data)
bt.Right.InOrder()
}
}
1
/ \
2 3
/ \ / \
4 5 6 7
Printing with In Order traversal:
4 2 5 1 6 3 7
Level Order
So those are the main traversal methods using recursion. The main point here really isn't the recursion though, it's the use of stacks that determine we go to the next child instead of to it's sibling. Again, this is because we're calling the recursive function on the left and right children which means whichever of those gets called last gets it's stack frame 'stuck under' the next call and can't proceed until all those frames have been popped off. You could acommplish the same thing by creating your own stack and iterating through it, but using the call stack just makes for less code.
Let's look at one example of a Breadth First Search way of traversing the tree, Level Order traversal.
func (bt *BinaryTree) LevelOrder() {
queue := CreateQueue(100)
queue.Enqueue(bt)
for queue.Size > 0 {
node := queue.Dequeue()
if node != nil {
fmt.Print(node.Data)
if node.Left != nil {
queue.Enqueue(node.Left)
}
if node.Right != nil {
queue.Enqueue(node.Right)
}
}
}
}
Here, we create a queue that we'll use to line up our child nodes at each level to be printed and a loop that will continue as long as the queue has elements in it. We start by printing the first node in the tree (1), then queueing up it's left and right child (2) and (3), as long as they're not nil. On the second loop, we dequeue and print the first node in the queue (2), then add it's children into the queue. On the third loop, we dequeue and print the next thing in the queue which is (3), then add it's children (6) and (7) to the back of the queue. Again, this keeps going as long as there are child nodes being queued up. Since we're traversing the tree and printing at each level instead of following one direction down to the bottom first, we're prioritizing breadth over depth.
1
/ \
2 3
/ \ / \
4 5 6 7
Level Order traversal gives us this:
1 2 3 4 5 6 7
That's really all for a basic Binary Tree. You can pretty much apply this same logic to trees with any number of children but you might have to get fancy with deciding which child's path to follow when doing DFS.
BST (Binary Search Tree)
A Binary Search Tree is just like a regular binary tree except that each sub-tree is organized so that the parent node's left child is less than it and it's right child is greater than or equal to it. Searching, inserting, and deleting on BSTs is O(logn) on average because you're basically dividing the time needed in half on every iteration. Here's a really simple example of a BST:
2
/ \
1 3
Let's see how to insert values into it:
func (bst *BinarySearchTree) Insert(data int) *BinarySearchTree {
bst.mu.Lock()
defer bst.mu.Unlock()
node := &BinarySearchTree{
Data: data,
}
if bst == nil {
bst = node
} else {
if data < bst.Data {
bst.Left = bst.Left.Insert(data)
} else {
bst.Right = bst.Right.Insert(data)
}
}
return bst
}
Keep in mind that this method inserts a binary search tree as a child on another BST then returns a pointer to the BST that was just inserted. To do the insert, we first check if the tree is nil and if so, set our data as the root node to actually create the BST. If the tree has a node, we check to see if the value we want to insert is less or greater than that root. If it's less than our root, we call the insert function again on that left node with the new data (which will again check to see if the node it's being called on has a value or not, setting the node as a new child node if not but determining if it should go to the left or right child if it does). Same thing for the right side. The result is that, whenever we insert a value it will fall into a sorted sub-tree on the overall tree.
In the best case, we end up with what's called a Balanced Binary Search Tree, which in simple terms means that each sub-tree pretty much has two children to 'balance it out' (A more formal definition is that the difference in height between the left and right sub-trees of any node is no more than 1). Let's look at an example of an un-balanced BST to see how one looks:
10
/
8
/
3
If we started with (10), then added (8), the (8) would go to (10)'s left... then we add (3), but it can't go to (10)'s right so we add it as (8)'s left child. At this point, it's not even really a binary tree any more. It's basiccally a linked list. Because of this, we lose any traversal advantages of it being a BST, so what would have taken O(logn) now will take O(n).
Searching a BST is very similar logic to inserting into one. You start at the root node, check if it's the value you're looking for. If not, check if the value you're looking for is less than that node or greater than it. if it's less, go to the left and do the same thing on each child, if greater, go to the right and do the same on each child. keep doing that until you find it or come up empty. Since you're cutting the problem in half each time, it's average time complexity is O(logn).
func (bst *BinarySearchTree) Search(key int) *BinarySearchTree {
if bst == nil {
return nil
}
if bst.Data == key {
return bst
} else if key < bst.Data {
return bst.Left.Search(key)
} else {
return bst.Right.Search(key)
}
}
So that's pretty much the basics of Binary Trees and Binary Search Trees!