Building Binary Search Trees in JavaScript
Some of the most popular interview questions involve traversing a binary tree to find a given value. When I first started to learn to program I would run across these algorithms for BFS(breadth-first search) and DFS(depth-first-search) and as I tried to understand them, I inevitably would be stumped by something referring to ‘node.left’ or ‘node.children’. I didn't know what a node was outside of the context of nodes in HTML and definitely didn’t understand why they had a left and right value or what the tree is and where it came from. In this post, we will walk through what a tree is and where it comes from, as well as some of the benefits of using this data structure.
First, let's define binary. Binary means there only have two options, think 1s and 0s in computing, that's all you get, and everything is ONLY represented by a string of 1s and 0s. So in terms of a binary tree, we are creating a data structure that at point will only give up to two options to move to the next data point. To help me to understand this concept I started from the perspective of a binary search on a familiar data structure, like an array.
Let's take a look at an array of 13 numbers, and say we are searching for the number 45.
let arrayToSearch = [4,3,6,17,56,32,45,12,1,9,24,18,35] The first step is to order the array. We can not effectively do a binary search if the values are not in order.
let sortedArray = [1, 3, 4, 6, 9, 12, 17, 18, 24, 32, 35, 45, 56]The next step is to split the array in half. This is how we make this search binary, now we will have only two directions to go. Our median value in the ‘sortedArray’ is 17, so we ask, “Is the value we are searching for greater than or less than our median value?”. Since 45 is greater than 17, we KNOW that all of the values to the left of 17 do not need to be iterated through, as they are all less than 17. We can now imagine our array looking like this.
let sortedArray = [18, 24, 32, 35, 45, 56]Now we will repeat those steps until we find our value.
Find the median value, 32 or 35 will work since we have an even number of values.
Check if it is greater or less than the value we are searching for, 32 < 45.
Remove all the values to the left since it is less than our search value, and we are left with.
let sortedArray = [35, 45, 56]The median value is now 45, so when we check the value against our search value we see it is equal and stop the search, and that’s a binary search!
Ok so now that we hopefully have a better grasp on what binary means and how it applies to a search, we can move into building our binary tree.
First, we need to create a class for our nodes, then we will make our tree. Remember that ‘node.left’ thing I mentioned earlier? Well, this is where that comes from. Our class will need to hold three pieces of essential information, there are more things we could add or you may run into looking at other binary trees, but I will keep it as simple as possible here and just use left, right, and the value of the node.
class Node{
constructor(value) {
this.value = value
this.left = null
this.right = null
}
}In this class, we will set the value of the current node, and leave the left and right values set to null, values for these can be added as we add more nodes. Now we need to create a way to add values and a place to put them.
class Tree {
constructor(){
this.root = null
this.all = []
}
}Our Tree NEEDS a root attribute, but the ‘all’ attribute is an option, I am adding it here so if you build this you will have an easy way to see all of your tree’s values without having to write a function for it. We just need to make sure whenever we add a node, we also add its value to the ‘this.all’ array.
class Tree {
constructor(){
this.root = null
this.all = []
}
insert(value) {
let newNode = new Node(value)
if(!this.root){
this.root = newNode
this.all.push(newNode.value)
}else this.insertNode(this.root, newNode)
}
insertNode(currentNode, nodeToAdd){
if(nodeToAdd.value < currentNode.value){
if(currentNode.left === null){
currentNode.left = nodeToAdd
this.all.push(nodeToAdd.value)
}else this.insertNode(currentNode.left, nodeToAdd)
}else if(nodeToAdd.value > currentNode.value){
if(currentNode.right === null){
currentNode.right = nodeToAdd
this.all.push(nodeToAdd.value)
}else this.insertNode(currentNode.right, nodeToAdd)
}
}
}Ok, so lots of code here, let’s walk through it. We have two functions, ‘insert()’ and ‘insertNode()’. The first function says, if we get a value and the root of our tree is null, then set that value as the root, else call the second function to insert a node.
The Second function is taking two arguments, our ‘currentNode’ and our ‘nodeToAdd’. We check the value of our current node and compare it to the value we want to add. If it is less then we move left and if it is more we move right, as we did earlier with our simple binary search. Then we can check the value of the side we have chosen, let’s say it was less than and moved left, if the value of ‘currentNode.left’ is null that’s where we add the new value, if not then we start the process over but change the ‘currentNode’ value to ‘currentNode.left’ to move us further through the tree. Once we find a null value through this process we can add the ‘nodeToAdd’ there. You can copy and paste all of this code, then run the code snippet below to see that we have values going into our tree.
const tree = new Tree()
tree.insert(54)
tree.insert(20)
tree.insert(24)
tree.insert(19)
tree.insert(60)
tree.insert(72)
tree.insert(58)This will create a tree that looks like this
54
/ \
20 60
/\ /\
19 24 58 72There you have it, a binary tree. We can add so much functionality to our tree class from here. Things like finding the smallest or largest value in the tree, checking if a value exists, and removing elements without creating gaps in our tree, I will leave those for another day.
To wrap up here I’d like to address the question “Why the heck do we even need a tree?!”. I know, why not just put it all in an array and use the methods the language provides to find, add, remove, and filter the values we need? Well, that's just fine if you only have a few values, but when you start dealing with hundreds of thousands of data points working with an array quickly becomes too slow, because we have to iterate through so many values to get our answer.
The tree reduces the number of steps we have to take to get to a particular value significantly. In the example above it would take a maximum of two steps to find any value in the tree, and on top of that, we cut out half of the tree when we start our search. If the value we are searching for is less than the root we can eliminate the entire right side of the tree and vis-versa if the value was greater than the root. If we had the same seven values in an array, it could take up seven steps to find a value, AND there are no rules that reduce our options. Again, this won’t make much difference with such a small data set but I hope you can see the value of splitting a number like one million in half and continuing to split it each step of the way. Finding our value in our data set of one million will reduce to 500,000, then 250,000, then 125,000, and so on, it will only take ten steps to reduce our potential choices to 977. If we took ten steps via the array iteration we would still have 999,980 choices.
So in short creating a tree can solve a huge time complexity problem when iterating through large datasets. It’s not something you will run into every day, but it is definitely a popular interview question, and understanding binary search on an array is a really practical place to start, the actual building of a tree will come into play when it is necessary. Just keep coming back to the topic and know that if you have a large data set you you've got a great place to start working.
