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

Image for post
Image for post

Traversing through a BST

Implementing BFS

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 treereturn 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 situationconsole.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

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

Pre-order Traversal

const preorder = (root) => {if(!root.value){//return null if the root node given is emptyreturn 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

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

Post-order traversal

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

Time and space complexity of DFS

Summary

References

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store