Introduction of Binary Search Tree in Javascript

Learning the uses of trees and specifically binary search trees with javascript implementation

Early on in our journey in software development, most of the data structures we encounter are linear. The common ones are arrays, strings perhaps linked lists or even stacks and queues. Depending on the programming language of your choice, some of the data structures mentioned can have varying degrees of similarity. They are relatively easy to understand, and they help us become familiar with the tools that the specific programming language offers. However, linear data structures most definitely do not take care of all of the problems we need to solve, not only in the CS(computer science) world but in the real world as well.

This is where trees come in. Like many things in nature, trees are a hierarchical structure. You must have heard of the DOM tree. As the name suggests, it is a tree of document object models. The file system in your computer is in a tree structure. If you wanted to find a specific ancestor of yours, it would be in a tree with you at the root. Today, we are going to look specifically at a type of tree, binary search tree.

Introducing BST

A binary tree is a tree where each node has a maximum of two children nodes. A binary search tree is a type of binary tree where for each node, the left child is smaller than the root and the right child is greater than the node. In other words, the binary search tree is a sorted tree. Because of the recursive nature of tree structure, every child node is a binary search tree itself as you can see from the example BST below.

Traversing through a BST

There are typically two ways to traverse/search through a binary tree. One is called the breadth-first search(BFS), and the other is called the depth-first search(DFS). You might think to yourself, these are the terms that I hear people say when talking about graphs? You would be right because a tree is just a special type of graph. Later, we will see the implementation in javascript, but the concept/algorithm should be easily applicable and translatable to any other language.

Implementing BFS

The following is the javascript implementation of BFS. The code also includes the implementation of the basic structure of each node in a tree and a queue. This assumes a basic understanding of the queue data structure. Assuming the initial root node given is not empty, we print out the value in the node while pushing its children into the queue from left to right(the order does not matter here as long as it is consistent). From this point on, we will only be pushing further children into the queue while popping what is already in the queue to print. Because of the nature of the queue, each level will be printed in order.

class node{
constructor(val){
this.value = val;
this.left = null;
this.right = null;
}
}
class queue{
constructor(){
this.value = [];
}
enqueue(val){
this.value.push(val);
}
dequeue(val){
return this.value.shift(val);
}
front(){
return this.value[0];
}
empty(){
return this.value.length === 0;
}
}
const BFS = (root) => {
if(!root.value){
//returns null for empty tree
return null;
}
let q = new queue();
q.enqueue(root);
while(!q.empty()){
let current = q.front();
q.dequeue();
//we console.log the value here to print out each value
//but you can replace this with any other operation
//fit for the situation
console.log(current.value);
if(current.left !== null){
q.enqueue(current.left);
}
if(current.right !== null){
q.enqueue(current.right);
}
}
}

The time taken to traverse each node is constant. We only traverse each node once; therefore, the time complexity of this traversal is O(n). However, the space complexity has the best case O(1), but that is seldom the case since we will not always get a tree with each node having only one child. The average and the worst case for space complexity is O(n).

Implementing DFS

As we have seen, the following code is the node structure that makes up a tree. I will leave this here for reference as it is used in all 3 kinds of DFS. They are pre-order, in-order and post-order traversals. They will be explained in detail below.

class node{
constructor(val){
this.value = val;
this.left = null;
this.right = null;
}
}

Pre-order Traversal

The first kind of depth-first search we will be implementing is preorder traversal. As the name might suggest, we will print each node’s value first and traverse to the left followed by traversing to the right. When thinking about this on one node, the procedure might seem quite static, but when applied to the entire tree/all nodes, the process is recursive. When you arrive at a node, you first print the value, then you look for whether the left child exists before looking for the right child. You traverse down the tree by recursively calling the child nodes on the left and the right in the desired order. The implementation is as follows.

const preorder = (root) => {
if(!root.value){
//return null if the root node given is empty
return null;
}
console.log(root.value);
preorder(root.left);
preorder(root.right);
}

The pre-order traversal can be used when trying to make a copy of a binary tree.

In-order traversal

The in-order traversal is quite commonly used as it follows the order of a binary search tree. Quite similar to pre-order traversal, in-order traversal only changes when we print the current value. In-order traversal is one of the most efficient methods to determine whether a binary tree is a binary search tree.

const inorder = (root) => {
if(!root.value){
//return null if the root node given is empty
return null;
}
inorder(root.left);
console.log(root.value);
inorder(root.right);
}

Post-order traversal

The post-order traversal takes printing the current value to the end of the cycle. You check the left child first, then the right child and finally printing the current node. We can use this method to delete the tree.

const postorder = (root) => {
if(!root.value){
//return null if the root node given is empty
return null;
}
postorder(root.left);
postorder(root.right);
console.log(root.value);
}

Time and space complexity of DFS

Since we have only one function call for each node, the time complexity for all three DFS is O(n). However, the space complexity for these algorithms is the height of the given tree. That can vary depending on what the tree looks like. The height in the worst case would be the number of nodes minus 1. The space complexity for that would be O(n). But, that is not always the case, hopefully. The best case, which also happens to be the average case, is O(log(n)).

Summary

We just went over the basic concepts of a binary tree, binary search tree and the implementation of the algorithms for traversals in javascript. Hopefully, next time you encounter a problem that is related to the binary search trees, these tools can help solve it.

References

Binary search tree