September 28, 2017

So. I’ve tried out a couple of coding tests and one thing I keep seeing is the Binary Search Tree 😰 (“Goes on web hunt”).

I created a simple JS tutorial with an implementation of the Binary Search Tree and some methods based on the knowledge gathered on the web hunt 😼.

A Binary Search Tree is a data structure that stores their objects with the keys in a sorted order so that lookup and other operations use the principle of Binary Search - When adding or looking for a key, traverse the tree from root to leaf, comparing the keys stored in the nodes of the tree and deciding, based on the comparison, whether to continue searching in the left or right subtrees.

On average, each comparison allows the operations to skip about half the tree, so that each operation takes the time proportional to the logarithm of the number of items stored in the tree. Much better than linear time required to find items by key in an unsorted array, array, but slower than the corresponding operations on hash tables (Which is probably something we’ll be looking at next time).

Create a js file and try these out to see the Binary Search Tree in action! 😬 😎 🤓

Create a node:

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

Create a constructor for the Binary Search Tree:

```
function BinarySearchTree() {
this.root = null
}
```

The structure of a Binary Search Tree is as follows:

- Every node value on the left is smaller than the parent node (root)
- Every node value on the right is larger than the parent node (root)

This would require you to find the appropriate location when inserting.

Create the push method to check the node values and insert the value in the correct position:

```
BinarySearchTree.prototype.push = function(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.value) {
if(!currentNode.left) {
currentNode.left = newNode
break
} else {
currentNode = currentNode.left
}
} else {
if (!currentNode.right) {
currentNode.right = newNode
break
} else {
currentNode = currentNode.right
}
}
}
}
```

Once you have that, you can now create an instance of a Binary Search Tree and push values to it! 😃

Create an instance:

` var bst = new BinarySearchTree()`

Push some values:

```
bst.push(40)
bst.push(25)
bst.push(10)
bst.push(32)
bst.push(78)
```

Now lets create some methods to traverse the tree and get the minimum and maximum values 😊

Traverses the tree from the parent node and visits the left side of the tree, left subtree-first, then proceeds to the right subtree.

So the values after the pre order traversal would correspond to:
`40, 25, 10, 32, 78`

```
function preOrder(node) {
if (node) {
console.log(node.value)
preOrder(node.left)
preOrder(node.right)
}
}
```

Traverses the tree from the deepest left subtree, in order from smallest to largest value.

So the values after the in order traversal would correspond to:
`10, 25, 32, 40, 78`

```
function inOrder(node) {
if (node) {
inOrder(node.left)
console.log(node.value)
inOrder(node.right)
}
}
```

Traverses the deepest levels of the subtrees, left to right of the subtree, eventually reaching the parent node.

So the values after the post order traversal would correspond to:
`10, 32, 25, 78, 40`

```
function postOrder(node) {
if (node) {
postOrder(node.left)
postOrder(node.right)
console.log(node.value)
}
}
```

Now lets call all the above methods and log a nice message above each one so we know which results we’re looking at!

```
console.log("Pre order traversal: ");
preOrder(bst.root)
console.log("\nIn order traversal: ");
inOrder(bst.root)
console.log("\nPost order traversal: ");
postOrder(bst.root)
```

Sweet! The values log as expected. Now let’s create some methods to get the minimum and maximum values form the tree.

Gets the smallest value from the tree:
`10`

```
function minNode(node) {
if (!node) {
return 0
}
if (node.left) {
return minNode(node.left)
}
return node.value
}
```

Gets the maximum value from the tree:
`78`

```
function maxNode(node) {
if (!node) {
return 0
}
if (node.right) {
return maxNode(node.right)
}
return node.value
}
```

Lets log the minimum and maximum values:

```
console.log("\nMin Value: ");
console.log(minNode(bst.root));
console.log("\nMax Value: ");
console.log(maxNode(bst.root));
```

Awesome! 😬 😬 😬

I hope this cleared the air about Binary Search Tree’s in even the slightest bit!

Check the Github repo for this tutorial:

Check these out for some further reading (It’s what the tutorial is based off of):

Happy Coding!!! 👽 🤓 👾

By **Taariq** who lives in Cape Town. He also happens to computer alot. You should probably follow him on Twitter