## What is a binary search tree?

A binary search tree is a data structure that quickly allows us to maintain a sorted list of numbers.

It is called a binary tree because each tree node has a maximum of two children.

It is called a search tree because it can be used to search for the presence of a number in O(log(n)) time.

The value of the key of the left sub-tree is less than the value of its parent (root) node's key. The value of the key of the right sub-tree is greater than or equal to the value of its parent (root) node's key.

The logic being lower value as compared to the parent node should always be on the left.

Here is an amazing site to visualize the different operations on Binary Tree and other data structures visualgo

## Operation on Binary Search Tree

- Insertion
- Search

## Insertion

When a value is to be inserted, we must first find its proper location.

- First we have to check if there exists a root node if not we insert the value at the root.
- If we have a root value then we check if the value is less or greater than the parent node.
- If the value is less than the parent move to the left and check if the location is empty if not do a greater than or less then check with that value and move either to the right or left. if you find an empty location with the criteria above insert the value. 4 return the tree when done.

Code implementation in JavaScript:

```
class Node{
constructor(val){
this.val = val;
this.left = null;
this.right = null;
}
}
class BST{
constructor(){
this.root = null;
}
insert(val){
let newNode = new Node(val);
if(!this.root){
this.root = newNode;
}else{
let current = this.root;
while(true){
if(val < current.val){
if(current.left === null){
current.left = newNode;
return this
}else{
current = current.left;
}
}else{
if(current.right === null){
current.right = newNode;
return this
}else{
current = current.right
}
}
}
}
}
```

In Python:-

```
class Node:
def __init__(self,val):
self.val = val
self.left = None
self.right = None
class BST:
def __init__(self):
self.root= None
def insert(self, val):
newNode = Node(val)
if self.root == None:
self.root= newNode
else:
current = self.root
while True:
if val< current.val:
if current.left == None:
current.left = newNode
return self
else:
current= current.left
else:
if(current.right == None):
current.right = newNode
return self
else:
current = current.right
```

There is an issue that arises when implementing a BST. That is how do you handle equality. This is an edge case and the person implementing the BST might have to make a decision that best suits them, from either ignoring it outright or returning `undefined`

or `null`

or `None`

. My choice was to insert on the right always if equality is ever encountered.

Next on the series, I will implement the search functionality.

## Top comments (0)