In this weeks continuation of data structures, I’ll be going over how to build out a binary search tree along with some simple traversal algorithms to go along with it. I’ve written about BST traversal before, but I realize it may not be as clear as it could be. So we’ll revisit that in todays blog as well!
A little review…
We can typically view trees having a few characteristics that, well, make it a tree. We’ll focus on the root, nodes, and subtrees to keep it high level for now. If you look at the picture above, each of the circle (depending on where you are) is considered to be the root and anything else can be viewed as a node/key. A little confusing, but imagine that this is a board game called “sugary edible rocks land” and each circle is where you can move you marker. If you start at 7, thats considered the current “root” , with 5 and 12 being the nodes, and everything below 5 is the left “subtree”, where everything below 12 is the right “subtree”. If you move your marker to the 5 for what ever reason, thats technically the new root with 3 and 6 being the new node, and only a left subtree (1 and 4 below the 3 root) since 6 doesn’t have anything under it.
I know this is a lengthy and wordy read
There are many different types of trees out there with varying characteristics, but as the title states, we’re interested in the Binary Search Tree (BST). So what is the definition of a BST? Well in laymen terms, the data/key in the left subtree of the root should be less than the root, and the data in the right side subtree should be greater than the root. As you stare hard at the example above, you can see how it’s structured to this rule! If you start at 7(root), every node/key to the left is smaller than 7, and every node/key to the left is greater. Head down to the second level and look at the 12 as the root. The subtree to the left of 12 is smaller, and the subtree to the right is larger.
Why are BST important and how are they useful?
According to Wikipedia, “Binary search trees allow binary search for fast lookup, addition and removal of data items, and can be used to implement dynamic sets and lookup tables. The order of nodes in a BST means that each comparison skips about half of the remaining tree, so the whole lookup takes time proportional to the binary logarithm of the number of items stored in the tree.” This is pretty self explanatory, but now that you understand the power of this particular data structure, let’s jump into some code and build one out!
First let’s build out a class and constructor for when we want new trees
We want to initialize a tree with just a root with the left and right pointing to null. The next step would be building out some class functions to helps us insert some new nodes.
Here we have a class function called insert which takes in a value, and starts doing some logic checks. Simply put, it’ll check if the the newData is less than this.data (our original root) and also see if we have a left node. If we have a left node, then it’ll recursively keep checking until we no longer have a left node and append it as the new node! Same concept works for the right side except it’s checking if the newData is bigger. Another helpful class function is to search our trees after we’ve constructed them with a some values. Let’s create a class function called contains().
So as mentioned, the image above is the implementation of the search method. We are also going to recursively traverse through the tree depending on whether the target value is larger or smaller than the root. This is similar to the binary search concept implemented on arrays. We only need to traverse and look in the left or right subtrees meaning a better time complexity. As usual, there is the preOrder, inOrder, postOrder traversal that you can do as well.
This might look familiar and it should, I’ve written about it before except this is just a class function. Note, if you want to tweak the method to instead of console logging it, just create an empty array, push(this.data) and return the array. I hope you enjoyed the read and this helps you strengthen your knowledge on BST!
