Learning Binary Search Trees

A binary tree in the wild

Learning about data structures beyond the ones that are built into JavaScript(like arrays and object literals) has been a blast. Aside from being essential knowledge for a developer to possess, I am really enjoying creating the custom classes for each data structure along with the methods that make them work. Trees, specifically Binary Search Trees(BST) are the most interesting ones that I have learned so far, and I’m excited to share the knowledge that I have gleaned. In this article, I will be delving into what a tree is, some of the real-world applications of trees, and the big O of a couple of important operations in BSTs. A lot of the information and images in this article will be coming from my repl where I built out a class for a BST and the nodes that it consists of.

Trees as a data structure are so named because when visualized, they resemble a tree(usually an upside down one). A tree is comprised of various nodes that have a parent-child relationship. There is typically a single root node that has pointers to the other nodes further ‘down’ the tree. Trees are similar to Linked Lists in that they consist of nodes that point to each other, but they are less linear. Literally. In a Linked List, there is just one way to go through the data, from front to back(or back to front as well if it is a Doubly Linked List). There are many different kinds of trees, just like in real life. This article will be focusing specifically on BSTs.

A couple of simple rules are what differentiate a Binary Search Tree from any old tree. They are as follows:

1. Each node can have no more than two child nodes.
2. Every child node that is on the left of its parent must have a lesser value than its parent.
3. Every child node that is on the right of its parent must have a greater value than its parent.

While these rules do limit what you can put into your tree and where, they make BSTs an extremely useful and efficient data structure for dealing with sorted data. If you want to find a specific node, each level down the tree that you go eliminates half of the possible remaining nodes. This also means that adding another level only increases the maximum amount of steps to find a node by one.

Without further ado, lets take a look at how to build a BST in JavaScript!

With this simple setup, you have a fully functional node, and the skeleton of a BST that methods can be added to. Because of the nature of BSTs, the two most important methods to add are insert and find. We need to be able to add a new node to the BST and ensure that it is in the right place, and we need the ability to find nodes once they are in there. Both of these methods will accept a value, and iterate through the tree.

And that’s it! This is a totally valid BST. While there aren’t too many class methods, BSTs are really meant to do a couple of things very well. This brings us to the final part, the big O of BSTs.

Insertion: O(log n)

Searching: O(log n)

check out bigocheatsheet.com for more great information

Thanks for reading!