Binary Search Tree in Javascript

Photo by Aaron Burden on Unsplash

Last time with my data structure journey, we talked about a tree’s fundamental data structure, which includes a tree data structure in general and the basic terminology of a tree. There are variations of tree data structures out there, but we will talk about the famous binary search tree in this article.

What is a Binary Search Tree?

First of all, we need to know what a binary tree is? A binary tree is each node of the tree at most two children; it can be one, zero, or two but not three. A binary search tree (BST) is a particular case of a binary tree, where the tree values are sorted in a specific way. They are kept in order and used to store data that can be compared. Usually, the data are numbers, and the way BST works is the root node of the tree to the left side. All the nodes should be less than the root number.

Left: Binary search tree vs. right: Binary tree

On the other hand, the tree’s root node to the right side; all of the nodes should be greater than the root number. It can also repeat on each child node. For instance, below the BST picture, 10 is the root. The inserting node of 6 should be to the left of the tree due to less than 10. Inserting a node of 15 is greater than 10, so to the tree’s right. For instance, each node is the same process; inserting a node of 8 is greater than a node of 6, so the node will be to the right side of the node of 6. Inserting node of 3 is less than a node of 6, therefore to the left side.

In summary, what BST requirements are, first, every parent node has at most two children; second, every node to the left of a parent node is always less than the parent. Third, every node to the right of a parent node is always greater than the parent. Just remember that BST data is kept in a particular order. Every node and every child to the right is greater than a parent node; every piece of data to the left is less than the parent node.

Implementation

Before implementing BST, we need to have a binary search tree class and a node class to create a tree, similar to a linked list. We had the link list class and then a node.

BST itself only has one important property, which is the root. Its node has its own value, and instead of .next or .prev ,here we .left and .right.

Class implementation of a tree; very similar to a linked list, but instead of next and prev, we have right and left. Also, more importantly, the tree has the root property.

The way we create the BST, we need to insert a node to the tree. Start with the root and check if the value you want to insert is less, go left. If it is more, then go right. If the value already exists, return undefined. In terms of complexity, BST is fast, Olog(n) best case, and average, it is very close to constant time. However, a worse case is not guaranteed since a tree could look like a linked list, with only one side of the tree node; the time complexity would be O(n). The below picture shows the implementation of tree insertion in BST.

Insert a node implementation in a tree; This returns BST.

So there you go! That is a binary search tree, Thanks again for reading and until to the next data structure journey!