Nerd For Tech
Published in

Nerd For Tech

Let’s Build a Binary Search Tree with JavaScript

Build your own at https://visualgo.net/en/bst

What is a Binary Search Tree (BST)?

A BST is a node-based, ordered, tree data structure in which each node can have a maximum of two children. These are children are known as the left node and the right node. The left node will always be less than its parent node, and the right node will always be greater than its parent node. The top node is known as the root node. So with this in mind, if any descendant of the root node on its left is greater than the root node or if any descendant of the root node on its right is less than the root node, the binary tree would be invalid.

Nodes can have only 0, 1, or 2 children. A node without any children is known as a leaf or terminal.

When a value is inserted into a BST, the root node is checked to see if the inserted value is greater or less than the root value. If less, the value is sent down to the left, and if greater sent to the right. If a node already exists, the same comparison is run again to determine if the value should be sent down to the left or right side of the existing node. If there isn’t already a node where the value is being sent, a new node (leaf, terminal) is created.

Types of Binary Search Trees

Full Binary Search Tree: In this BST, each node will have either 0 or 2 children:

A Full Binary Search Tree

Complete Binary Search Tree: All nodes on the tree have the maximum number of child nodes except for the nodes on the last (or bottom) level:

A Complete Binary Search Tree

Perfect Binary Search Tree: A perfect BST tree is both Full and Complete. All nodes are full except for the nodes on the bottom level, they will all be leaves:

A Perfect Binary Search Tree

Let’s Build a BST

Now that we have a solid grasp on what a BST tree is, let’s use JavaScript to build one from scratch! We will create nodes and a tree using classes:

We instantiate a new Node with a value. The Node has pointers for the value, left and right. A new BST instance will have a root with a value of null. Let’s add a method to the BST class that will allow us to insert a value into our tree:

Whew! Ok, let’s take this nice and slow. Our insert() method is using recursion to search the binary search tree for where our new data should be appended. The first thing being checked in the insert method is if our BST root is still null. If null, it means this is the first time insert has been called to insert data into the tree. Therefore, a new Node will take the data as its value and will be inserted as the root node of the tree. The next time insert is called, it will fail the first “if” statement and go to the else portion of the method. Here we set the tree’s root to the constant “node”. We then create a method that will search the tree to see where the data should go. The newly created searchTree method is then invoked, taking in the node constant as its argument. The searchTree method first checks if our data is less than the current node’s value and if there is a value to the left side of the current node. If both are true, we use recursion and call the function again, this time taking that left node as the argument. If false, we move down to the next condition. If the data is less than the current node’s value (and we know node.left doesn’t exist because the previous conditional wasn’t true), we can instantiate the node.left as a new Node with our data. However, if our data is greater than node.value, then those first two conditionals will fail and we will go to the last two conditionals. These do the same thing as the first two except they are checking where the new node with the inserted data should append to the right half of the tree.

Searching for a Value

Binary Seach Trees are sorted in a way that usually can cut our search time in half since we only have to search half of the tree. They are useful for storing any data that can be compared using less than or greater than. In the best cases, the implementation of a BST has a Big O time complexity of O(log(n)). In the worst cases, it has a linear O(n) time complexity, which is still really great.

To search if a specific value exists in the tree, let’s create another method called find() in the BST class that will return a boolean indicating if the data was found or not:

The first thing find() does is check to make sure there is a root value. If there is, we set “node” as the root and “found” as false. Then using a while loop that runs only if “node” is true and “found” is false, we use conditionals to check the tree for the data we are looking for. Starting at the root, we compare it with the data to see if we should traverse down the left or right side of the tree. After we can travel no further, found will be set to node. If the node exists, “found” will be set to the node and become true, causing the loop to stop. If the node doesn’t exist, “node” will become false and the loop will stop. We then use a ternary statement to return if found is true or false.

Conclusion

This was a simple introduction to the world of Binary Search Trees. There are many much more complex things you can do with them, and here are some links to keep you going:

As always, thanks for reading! Feel free to connect with me on LinkedIn!

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Kyle Farmer

Kyle Farmer

Sound Engineer to Software Engineer