Wednesday, July 11, 2018

[JAVASCRIPT] Binary Search Tree, Overloading prototype and implementing a map function

BST - Binary Search Tree

Hello, today I will show you how to develop the binary tree class and how to add a map method, along with the other common methods. We use the map method very frequently with JS Arrays. So I thought we can add it to the BST class we create. 

What is the map method?

The JS Array provides many intersting methods, that take as parameter a function and apply it over the data. We have map, filter etc. which are very useful for Array mutation.
Let us see the map method in action:

Consider this code snippet

var vals = [5, 6, 7, 8];
vals.map(val => val = val * val);

So what is the output ?

console.log(vals);

// You get [25, 36, 49, 64]

Do you see what happened?

val => val = val * val;

Breaking it down,

for every val in vals{
    val = val * val;
} //Not actual JS syntax


So we just saved ourselves from writing the for loop. And since this map function takes a function as a parameter, we can mutate the array however we need to.

I personally am trying to make this post a little easier to comprehend as I too was really confused with the syntax of JS and usage of => , but now I know to use it well and it helps me arrive at solutions much quicker. Filter works in a similar manner.

Now let us get our hands dirty with the code for BSTs:

First we need the Node class, defined by this function.

function Node(val){
  this.val = val;
  this.left = null;
  this.right = null;
}

Next we need the BST class, defined like so.

function BinSearchTree(){
  this.root = null;
}

Next, we overload all the functions we need like so.

push to add values to the BST

BinSearchTree.prototype.push = (val) => {
  var root = this.root;
  if(!root){
    this.root = new Node(val);
    return;
  }
  var currentNode = root;
  var newNode = new Node(val);
  while(currentNode){
    if(val < currentNode.val){
      if(!currentNode.left){
        currentNode.left = newNode;
        break;
      }
      else{
        currentNode = currentNode.left;
      }
    }
    else{
      if(!currentNode.right){
        currentNode.right = newNode;
        break;
      }
      else{
        currentNode = currentNode.right;
      }
    }
  }
}

toString using in-order traversal.

BinSearchTree.prototype.toString = () =>{
  var cur = this.root;
  var s = [];
  var done = false;
  while(!done){
    if(cur){
      s.push(cur);
      cur = cur.left;
    }
    else{
      if(s.length > 0){
        cur = s.pop();
        console.log(cur.val);
        cur = cur.right;
      }
      else{
        done = true;
      }
    }
  }
}


find to search for a key element

BinSearchTree.prototype.find = (key) =>{
  var cur = this.root;
  var s = [];
  while(1){
    if(cur){
      s.push(cur);
      cur = cur.left;
    }
    else{
      if(s.length > 0){
        cur = s.pop();
        if(cur.val == key){
          return true;
        }
        cur = cur.right;
      }
      else{
        return false;
      }
    }
  }
}

map applies a function over the array extended to BST

BinSearchTree.prototype.map = (d) =>{
  var cur = this.root;
  var s = [];
  var done = false;
  while(!done){
    if(cur){
      s.push(cur);
      cur = cur.left;
    }
    else{
      if(s.length > 0){
        cur = s.pop();
        cur.val = d(cur.val);
        cur = cur.right;
      }
      else{
        done = true;
      }
    }
  }
}


So these are the methods I developed. If you notice, the methods have a very similar structure with minor changes to the core operation. If you have any comments, please be sure to leave them below!

Here is some starter code to test the Implementation.

var bst = new BinSearchTree();
for(let i=0; i < 10; i ++){
  bst.push(parseInt(Math.random()*10));
}
bst.toString();

console.log(bst.map(x => x = x* x));
bst.toString();