Breaking Down a Binary Search Tree

One of the most import concepts to understand when it comes to data structures is a Binary Search Tree or BST. A Binary Search is simply a way that will allow us to maintain a sorted list of numbers.

Its called a Binary Tree because each node is only able to have up to child nodes each.

Here you will see that the root node 19 has two child nodes, and node 21 has one child node which is 25

Being called a Search Tree is in reference to search of a number in 0(log(n)).

With each BST are some things to rememeber:

• The very first value passed in into the BST is going to be your root value.
• The next thing to keep in mind is there is a left and right side to all nodes in the tree. If the next value passed into the BST is larger than the the parent node, that "child" node will form on the right side, and if the next child is less than the parent, that child node will form on the left side of the parent. Keep in mind those child nodes can potentially turn into their own parent nodes and will form their own trees as the same rules mentioned above are applied. When you look at tree with a bunch of nodes, you will notice that everything on the left side is always smaller than every thing on the right side of the tree.

There are two operations I will focus on which are insert, and find.
But first...

When starting a BST, you will have to classes, a node class, and a BST class.

In the Node class

class Node{
  constructor(value){
    this.value = value
    this.left = null
    this.right = null

  }
}

Your BST class will start with the falling:

class BST{
  constructor(){
    this.root = null
  }
}

Why the null assignments? By default your root, your left and right needs to be null until you start to traverse down the tree when inserting values. You cannot insert a left or right child first, if the root node is not defined.

Lets start building a tree!
Insert

The first operation is the insert operation. When inserting a new node, you need to create the node first.

class BST{
  constructor(){
    this.root = null
  }
 insert(val){
 let newNode = new Node(val)

 }

}

When inserting a node you need to set the base case of....."Does the root node exist?" If you answered no to this...the first node you insert will be your root node automatically. You also want to set a temporary variable.....I'll call it current in this case...and assign the root node to it.

class BST{
  constructor(){
    this.root = null
  }
 insert(val){
 let newNode = new Node(val)

 if(this.root === null){
      this.root = node
      return this
    }
 let current = this.root

 }

}

Next I am going to implement a helper function called whichSide(). What is going on here? Later on you you see how this is applied, but simply if you are not on one side of the current value or node in this case, you are obviously going to be on the other side and start traversing that way. eg are you on the left side, or on you on the right side of the current temporary value

class BST{
  constructor(){
    this.root = null
  }
 insert(val){
 let newNode = new Node(val)

 if(this.root === null){
      this.root = node
      return this
    }
 let current = this.root

 }

const whichSide = side =>{
      if (!current[side]){
        current[side] = node
        return this
      }
      current = current[side]
    }

}

Next is where we start placing the conditions based on the value and whether it goes left or right. The temporary value or the current value is always going to update to current parent node depending on how far you traverse down the tree fyi.As mentioned earlier if the value being inserted is less than the parent node, the child node node or val being inserted will fall on the left side, or else the value will fall on the right side.

class BST{
  constructor(){
    this.root = null
  }

  insert(val){
    let node = new Node(val)

    if(this.root === null){
      this.root = node
      return this
    }

    let current = this.root

    const whichSide = side =>{
      if (!current[side]){
        current[side] = node
        return this
      }
      current = current[side]
    }

    while(true){
      if(val === current.value){
        return this
      }

      if(val < current.value){
        whichSide('left')
      } else{ 
        whichSide('right')
      }
    }

  }

find
The find function is not very complicated as its only looking for a value you provide and just traversing down the tree until its located.

The first thing we need to catch is if the root node exist, because if the root node does not exist, then you will need to created tree for this to work and will just get false returned.

find(val){
 if (!this.root){
 return false
 }


}

Then just like in our insert function we need to setup a temporary variable.....we'll use current as the name again(has no relation to the one in my insert function). We also want create a variable that will be set to false initially. I high recommend this for convention purposes, otherwise you can just declare variable, and it will just be a "falsey" variable and it won't set off any errors in our compiler.

find(val){
 if (!this.root){
 return false
 }

 let current = this.root

 let located = false




}

Next we want to go into a loop as this is indicating it's traversing down the tree until the val is located or not. While there is a root value which there should be if you are using the find function, and is not yet located, you will jump to either the left or right side of the depending on the value you are passing in and the temporary(current) value being compared to will keep reassigning itself as it traverses down the tree until the value you are looking for is located.

find(val){
  if (!this.root){
    return false
  }

  let current = this.root

  let located = false

  while (current && !located){
    if (val < current.value){
      current = current.left
    } else if (val > current.right){
      current = current.right
    }else{
      located = true
    }

  }



}

Lastly...what if the value you are looking for does not exist after your algorithm went through the whole tree? You simply return false or whatever message you want to provide. If the value was located, you will return true.

  find(val){
  if (!this.root){
    return false
  }

  let current = this.root

  let located = false

  while (current && !located){
    if (val < current.value){
      current = current.left
    } else if (val > current.right){
      current = current.right
    }else{
      located = true
    }

  }

  if (!located) return "Doesn't exist in tree"

  return located


}

I hope this helps people in some way that need help understanding binary search trees. Any suggestion would be greatly appreciated.

Here is the full code if you need to see it all.

class Node{
  constructor(value){
    this.value = value
    this.left = null
    this.right = null

  }
}


class BST{
  constructor(){
    this.root = null
  }

  insert(val){
    let node = new Node(val)

    if(this.root === null){
      this.root = node
      return this
    }

    let current = this.root

    const whichSide = side =>{
      if (!current[side]){
        current[side] = node
        return this
      }
      current = current[side]
    }

    while(true){
      if(val === current.value){
        return this
      }

      if(val < current.value){
        whichSide('left')
      } else{ 
        whichSide('right')
      }
    }

   find(val){
  if (!this.root){
    return false
  }

  let current = this.root

  let located = false

  while (current && !located){
    if (val < current.value){
      current = current.left
    } else if (val > current.right){
      current = current.right
    }else{
      located = true
    }

  }

  if (!located) return "Doesn't exist in tree"

  return located

  }


}