Binary Search Tree

Within programming, there are many different Data Structures one of which is a tree. Then within that, there are many different types of tree structures. The tree data structure I am focused on exploring more for this post is the Binary Search Tree.

Photo by Adarsh Kummur on Unsplash

First some key points about all tree data structures:

• The topmost node is the root node there can only be one root node.
• Nodes on a tree point down to other nodes called child nodes.
• A parent node is a node pointing towards the child node.

Then for a tree to be a Binary Tree:

• Each node can only have two child nodes.

Lastly for a Binary Tree to be a Binary Search Tree:

• Of the two children nodes the node to the left has to be less than its parent node and the node to the right has to be greater than its parent node.
• So for a Binary Search Tree to be valid it has to follow all of the above bullets should be followed.

Below is a illustration of a very simple Binary Search tree

Binary Search Trees are very efficient data structures when it comes to searching and insertion, in terms of Big O both have O(log n) runtime for best and average case (there is a worse case that runs O(n) time if the tree only continually branches in one direction). So, in saying that here is the code in JavaScript for creating a Binary Search tree data structure class and node class I will then go through the insert and find functions.

The Binary search tree will know its root and each node for the tree will be initiated with a value and have a left and right associated with it.

Search

This is the code for the function for finding a node that will return true if the node is found or false if it isn't.

It first checks if there is a root node if not we know the tree is completely empty and there is nothing to find. However, if there are values in the tree we start at the root store it in a variable. Then create a while loop while there was a value in the variable we created to move left or right in the tree based on whether the value we are searching for is greater or less than the current node. This will return true if the node is found or it will return false if it reaches the end of a branch of the tree and the node wasn't found.

Insert

Here is the code for the function for inserting a new value into the tree in its appropriate location.

To start create a new node with the entered value. Then check if the tree root is empty if it is set the root to the created node and it’s done. Otherwise, like with the find function, we create a variable starting at the root that moves through the tree based on whether it is less than or greater than the variable to be inserted. Until we get a null value from the left or right(again based on whether it is less than or greater than the variable to be inserted) of a node and we place our new node there. The other exception here is if the value you are trying to insert already exists we just return undefined so there are no duplicates.

And that is a binary search tree with the search and insertion functions with the help of the Udemy course JavaScript Algorithms and Data Structures Masterclass I learned and have a better understanding of it.