Algorithms & Data Structures: Binary Trees (Unbalanced)

Introduction

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

Topic

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:

Source: Data Structures Succinctly Part 1 by Robert Horvick

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:

  1. There will always be a root node
  2. A node can have at most two children
  3. A node with no children is known as a leaf node
  4. 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
Source: Data Structures Succinctly Part 1 by Robert Horvick

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

ADD NODE:
As discussed above, adding a node is simple. Below is the code with some comments to guide your understanding

REMOVE NODE:
Now that we’re ready to remove a node from our tree, let’s identify scenarios we need to cover when removing a node.

Source: Data Structures Succinctly Part 1 by Robert Horvick

In this case, the left child replaces the removed node.

Source: Data Structures Succinctly Part 1 by Robert Horvick

In this case, 6 replaces 5 and 2 becomes a left child of 6 resulting in the following:

Source: Data Structures Succinctly Part 1 by Robert Horvick
Source: Data Structures Succinctly Part 1 by Robert Horvick

In this situation, the left child of removed right child, 6, takes the place of the removed node resulting in the following:

Source: Data Structures Succinctly Part 1 by Robert Horvick

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:

Source: Data Structures Succinctly Part 1 by Robert Horvick

Preorder Traversal
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

Postorder Traversal 
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
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

Conclusion

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.

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.