Algorithms & Data Structures: Binary Trees (Unbalanced)
Recently, I’ve decided to revisit some core computer science fundamentals and take a look at some of the most common algorithms and data structures. My background in college was MIS so we didn’t study much computer science theory or algorithms and data structures. Since I’ll be on the job hunt in the next few months, I thought it’d be a great idea to revisit some topics I had learned throughout the years and on the job. This post and subsequent posts titled “Algorithms & Data Structures I & II” are a review of the video series on Pluralsight but rewritten in Ruby. You can view the series here, assuming you have a Pluralsight account,https://www.pluralsight.com/courses/ads-part1&https://www.pluralsight.com/courses/ads2
In the following post, we cover the binary search tree covered in the Pluralsight course. The implementation is for unbalanced binary trees, and there will be a separate post for balanced trees. Please note, this is a prerequisite topic that must be fully understood before looking into balanced trees. The topics covered in this post are as follows:
- Binary tree functionality and overview
- Return of nodes
- Add and remove nodes from binary tree
- Different types of ways to traverse the binary tree
Binary Tree Functionality & Overview
A binary tree is a type of data structure. When we looked at the linked list data structure, we saw that the linked list behaved in a linear manner. Below is an example of a tree representing an organization chart:
From the image above, we can see there is always a root node, which is the board of directors in this example. A node can have children whose children can also have children. While the above isn’t a binary tree, the structure is very similar. Let’s look at some requirements that make up a binary search tree:
- There will always be a root node
- A node can have at most two children
- A node with no children is known as a leaf node
- When we add a node, we always start at the root node and if the value is smaller than the current node go to the left child and if the value is bigger or equal go to the right child until they become a leaf node
If we were to add the following values in order: 8, 4, 2, 3, 10, 6, and 7, what do you think our binary tree would look like?
- Since 8 is the first, it becomes our root
- 4 is small than 8 so it becomes 8’s left child
- 2 is smaller than 8 and 4 so it becomes 4’s left child
- 3 is smaller than 8 and 4 but bigger than 2 so it becomes 2’s right child
- 10 is bigger than 8 and becomes 8’s right child (since there are no other nodes on 8’s right)
- 6 is smaller than 8 but bigger than 4 and becomes 4’s right child
- 7 is smaller than 8 but bigger than 4 and 6, so it becomes 6’s right child
The Return of Nodes & Base BT Class
If you’re already familiar with linked lists, then the concept of nodes should be familiar, as they are identical in binary search trees.
Below is our initial binary tree class. Notice we want to pass in a root value when we first create our binary tree
Add & Remove Nodes
When it comes to adding a node, the process is fairly simple. We always start at our root node and compare the current node with the new node. If the new value is smaller, we go to the left, and if the new value is larger, we go to the right. Removing a node, however, is fairly complex; there are a few different scenarios that happen when we remove a node from our tree. Let’s first take care of adding a node
As discussed above, adding a node is simple. Below is the code with some comments to guide your understanding
Now that we’re ready to remove a node from our tree, let’s identify scenarios we need to cover when removing a node.
In this case, the left child replaces the removed node.
In this case, 6 replaces 5 and 2 becomes a left child of 6 resulting in the following:
In this situation, the left child of removed right child, 6, takes the place of the removed node resulting in the following:
With all three cases, we can start writing out the code. Like the add method previously, we’ll have a public method called remove. This method will find the node that needs to be removed AND the parent of that node. From here, we call our private remove method passing the node along the way.
Binary Tree Traversal
The final piece we need to look at are different ways we can read the binary tree. We have three different options when it comes to binary tree traversal. Below is the binary tree we will traverse:
With preorder traversal, we read starting from the root node, then all of the left children on the left side followed by the right children on the left side. After all the values have been traversed on the left side of the root, we repeat the same process on the right side of the root. The above binary tree is read in the following order: 4, 2, 1, 3, 5, 7, 6, 8. You can see from the code below we recursively call the method to find all of the left children first then work back up processing the right nodes
Like the name suggests, postorder traversal operates in reverse of the preorder route with the root being evaluated last. The above binary tree is read in the following order: 1, 3, 2, 6, 8, 7, 5, 4.
Inorder traversal is probably the way that will be most readable and easily understood as it displays nodes from smallest to greatest. The above binary tree is read in the following order: 1, 2, 3, 4, 5, 6, 7, 8
In conclusion, we’ve taken an extensive look at how binary trees are constructed, as well as the methods that all binary trees encompass. The above code samples and descriptions may have glossed over some minor details, but if you’d like to study this further in more depth, I advise you to either check out the Pluralsight courses or download the free PDF titled “Data Structures Succinctly Part 1 & 2” by Robert Horvick.