Binary Search Tree (BST)

Binary Search Tree is a type of data structure that basically stores values in a sorted order on the basis of comparison between 2 values.

It allows looking up items, adding new items and items removal quickly.

Each particular element inside the tree are called Nodes, they possesses 3 attributes:

Node Object

With this in mind, you can then imagine the structure of the tree as such:

With 10 as the root, you then pass it the value of 8.

Because 8 is smaller than 10, 8 goes to the left node of 10.

With the value 11, since its greater than 10, you would assign it to the right node.

As the next value come in, since 10 already possesses a left node and a right node, you would then pass it down to either 8 or 11 for comparison.

This is the foundation of Binary Search.

Binary search runs in logarithmic time in the worst case, making O(log n) comparisons, where n is the number of elements in the array, the O is Big O notation, and log is the logarithm. Binary search is faster than linear search except for small arrays. However, the array must be sorted first to be able to apply binary search. There are specialized data structures designed for fast searching, such as hash tables, that can be searched more efficiently than binary search. However, binary search can be used to solve a wider range of problems, such as finding the next-smallest or next-largest element in the array relative to the target even if it is absent from the array.

https://en.wikipedia.org/wiki/Binary_search_algorithm

It is considered highly efficient, as the ratio of the number of operations to the size of the input decreases and tends to zero when n increases.

Insert(val)

Once you pass in the first value, it will become the root.

Then if a root exist — as you pass in the next value AND while value does not equal to the current node (which should be the root right now), compare whether its less than or greater than the value of the current node.

Once determined, if lesser — the new value becomes the left node, else if greater — becomes the right node.

Insert(val)

Find(val)

Now why is this useful? In Binary Search Tree it is considered highly efficient when the sample size gets larger and larger.

What does this mean?

It means that as the tree gets larger, it becomes increasingly more effective to look for a specific value because as you dive each level deeper, the time of which it takes to look for the node would become less and less because of the comparison between two nodes. As it would continue the search in the same way in the left or right side.

Lets take a look:

Starting from the root, while current exist (which suggests the tree exist) —

Compare current to the input (val) If lesser, reassign current to the value of the left node, else reassign current to the right.

Run this process of comparison until val === current, return true if exist, else return false.

Traversal()

We can now display the entire tree as an ordered array using queue:

In computer science, a queue is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and removal from the other end of the sequence. By convention, the end of the sequence at which elements are added is called the back or rear of the queue and the end at which elements are removed is called the head or front of the queue, analogously to the words used when people line up to wait for goods or services.

https://en.wikipedia.org/wiki/Queue_(abstract_data_type)

Queue (abstract data type)

With this structure in mind, lets take a look at codes:

We begin by setting queue as an array that contains only the root node object.

We then declare a variable visited which will become the end result array.

while there are still nodes inside the queue array:

• Take out whats inside queue using .shift()
• Push that first item in queue into visited
• if there exist a left node, push it to the end of queue
• if there exist a right node, push it to the end of queue

Then return visited as end result.

As a whole:

Binary Search Tree Object

This was done using Breadth First Search(BFS), an algorithm for traversing the tree. It starts at the root and explore all of the nodes at the present depth before moving onto the next.

In opposite, there is also Depth First Search(DFS), which instead explores the node branch as far as possible before being forced to backtrack and expand other nodes.

Thank you for reading!