BST (Binary Search Trees) Defined

A binary search tree is basically a linked node list, or a node tree , the only main difference is how the tree is arranged.
To understand how a BST is arranged we first need to look at the types of nodes it holds:

Root node
Is the node at the very top of the tree, and even though its called a root its at the top of the tree.

Child node & Parent Node
If the a node is not a root node than its a Child Node of some other node that is a Parent node.
The only nodes that are not Parent Nodes are Leaf Nodes.
A regular node tree can have any number of child nodes, but in Binary Search Tree's the number of children is limited to only two.

Left Node & Right Node
The left node holds the a value that is lower than the Parent Node, and the Left Node hold a value that is greater than the Parent Node.
The Left Node and Right Node are also called Edges, and by following a certain edge yo can clearly travel down a path of lower or higher values then the node you looking at.

Path
Path is the series of edges you travel trough, and visiting all nodes in a tree in a perticular order is called tree traversal

Leaf Nodes
Leaf nodes have no Child Nodes, and thus they are not Parent Nodes either.

Levels
Levels are the maximum number of edges you can travel down the tree in one direction.
The root node is at level 0, the direct Child Nodes are at level 1, the children of all level 1 nodes are level 2 nodes, and so on...

 BST Insertion Procedure
The insertion procedure is made of a preperation stage prior to traversing the tree for insertion, and the traversing itself.
The preperations stage:
1) First we need to create a Node instance from the value we want to insert.
2) Then we need to position our selves in the root node of the tree, for that we will use a current variable, this variable will also be used to keep track of the current node were at at each traversal iteraton, if the root property of the BST is null then the tree is empty, we insert the node and exit the function.
3) Otherwise we start traversing the tree with a while loop, starting with the current root node.
The traversal stage
1) We by setting the parent variable to the current node.
2) If our value is smaller then the current nodes value, we set the the current node to the left node, keeping the parent node pointing to the previous current node.
3) If the new current node is null, we insert the new node here by changing the parent node's left property to our new node, otherwise skip to next iteration.
4) if our new value is higher the the current node, we set the current node to the right node, keeping the parent variable pointing to the previously current node.
5) if the new current node is null we insert and exit, otherwise we continue to the iteration.


an insert function might look something like this:

function insert(data) {
   var n = new Node(data, null, null);
   if (this.root == null) {
      this.root = n;
   }
   else {
      var current = this.root;
      var parent;
      while (true) {
         parent = current;
         if (data < current.data) {
            current = current.left;
            if (current == null) {
            parent.left = n;
            break;
         }
   }
   else {
      current = current.right;
      if (current == null) {
         parent.right = n;
         break;
      }
   }
}

BST Search procedures
Search procedures in computer science are recursive functions that travel the trees edges (left node, right node) in a certain order, for different purposes.
These certain orders of traversal are inorder, preoder and postorder. 
An in order function might look something like this:

searchBst(node){
   if(node === null) return;
   searchBst(node.left);
   showNodeValue(node);
   searchBst(node.right)
}

The stack that is opened here, first travel all the way down the left edges of the tree, then performs a procedure on each node, then opens up a stack for the right nodes. this way the lowest values are visited first.

in compersion see next slide.

BST Searching for the minimum & maximum value

Searching for minimum and maximum values with a binary search tree is quite simple.
For the minimum value you only have to travel the left edge of the tree.

function getMin() {
   var current = this.root;
   while (!(current.left == null)) {
      current = current.left;
   }
   return current.data;
}

For the maximum value you just have to travel the right edge:

function getMax() {
   var current = this.root;
   while (!(current.right == null)) {
      current = current.right;
   }
   return current.data;
}

BST Searching for a specific value

To search for a specific value you need to add a comparision fanction to decide which node to check next, the left or the right node.
 

function find(data) {
   var current = this.root;
   while (current.data != data) {
      if (data < current.data) {
         current = current.left;
      }
      else {
         current = current.right;
      }
      if (current == null) {
         return null;
      }
   }
   return current;
}