Binary Search Tree is one of the most commonly asked Data Structures in technical interviews. In this article, we will learn about what a binary search tree is and how to perform insertion into a node into a BST.

## What is a Binary Search Tree?

A binary search tree is a node-based data structure similar to a `Linked List`

. Where each node either has a `null`

value or holds a reference to another node in the tree which is called a `child`

node.

## Rules of Binary Search Tree

For a Tree data structure to be characterized as a BST it must meet all the rules of a tree data structure along with the following rules:

Each node in a BST should have at most two children.

The left subtree of a node can only contain nodes with keys lesser than its relative parent node's keys.

The right subtree of a node can only contain nodes with keys greater than its relative parent node's keys.

Meeting all the above rules, a basic binary search tree looks something like this:

Here, 32 is our `root`

node which has two `child`

nodes that are sorted as per the rules of a BST.

## Creating a Binary Search Tree in Javascript

Now that we know what is a BST and what are its rules. Let's now jump to the coding part and create a Binary Search Tree in Javascript.

The first thing that we need to do is define a `Node`

class, which will represent each individual node of a BST.

```
class Node {
constructor(val){
this.value = val;
this.left = null;
this.right = null;
}
}
```

Here, each node in our binary search tree will have 3 properties:

`value`

: the value of the node.`left`

: this will have reference to the left subtree of the node.`right`

: this will have reference to the right subtree of the node.

Next, we will create our BinarySearchTree class as follows:

```
class BinarySearchTree {
constructor(){
this.root = null;
}
}
```

`BinarySearchTree`

class will have only one property `root`

which will be the root of our BST.

We now have created our `BinarySearchTree`

class, let's see how we can insert nodes to our empty BST.

## Insertion in a Binary Search Tree

To insert new nodes to a BST we can either use the iterative approach or the recursive approach. In this article, I am using the iterative approach just for the sake of simplicity.

So let's first create the `insert`

method inside our `BinarySearchTree`

class, our insertion logic will go inside this method.

```
class BinarySearchTree {
constructor(){
this.root = null;
}
insert(val){
// Insertion logic will go here...
}
}
```

This method will take one parameter `val`

which will be the value that we want to insert into our BST.

Now, let's write our insert logic. The very first condition that we need to check is, if we don't have a `root`

present in our BST then the inserted node will become the root.

```
class BinarySearchTree {
constructor(){
this.root = null;
}
insert(val){
// Create a new node using the Node class that we created
const newNode = new Node(val);
if(this.root === null) {
// Save the newNode as the root
this.root = newNode;
// Return the entire BST and exit the function
return this;
}
}
}
```

We have our first condition covered. Now we can insert nodes into our empty BST and that node should become the root of the BST.

```
const BST = new BinarySearchTree;
BST.insert(32)
```

The above code should add a new `root`

to the BST if it is empty.

If it already has a root, we need to write a condition to check if the `val`

that we are inserting is less than the `root`

value.

```
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(val) {
const newNode = new Node(val);
if (this.root === null) {
this.root = newNode;
return this;
}
// Create a temporary variable which will keep track of the current node that we are at, by default it will equal to this.root
let current = this.root;
// Traverse over the tree
while (true) {
// If the new value is less than the current value
if (val < current.value) {
// Check if there is no left node
if (current.left === null) {
// Save the newNode as the new left node
current.left = newNode;
// Return the entire BST & terminate the loop
return this;
} else {
// Else if there is a left node
// Move current to current.left and repeat the entire steps again
current = current.left;
}
}
}
}
}
```

Then, we will write a condition to check if the new `val`

is greater than the `root`

value.

```
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(val) {
const newNode = new Node(val);
if (this.root === null) {
this.root = newNode;
return this;
}
let current = this.root;
while (true) {
if (val < current.value) {
if (current.left === null) {
current.left = newNode;
return this;
} else {
current = current.left;
}
} else if (val > current.value) {
// If val is greater than root.value
// Check if there is no node to the right of the root
if (current.right === null) {
// Save the newNode as the new right node
current.right = newNode;
// Return the entire BST & terminate the loop
return this;
} else {
// Else if there is a right node
// Move current to current.right and repeat the entire steps again
current = current.right;
}
}
}
}
}
```

One last thing that we need to check is the edge case that is, if we are trying to insert a duplicate value. There are lots of ways to handle this but in our case, we will return `undefined`

if we try to insert a duplicate value to the binary search tree.

```
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(val) {
const newNode = new Node(val);
if (this.root === null) {
this.root = newNode;
return this;
}
let current = this.root;
while (true) {
// Base condition: If val is equal to current.value which means it is a duplicate value
if(val === current.value) return undefined;
if (val < current.value) {
if (current.left === null) {
current.left = newNode;
return this;
} else {
current = current.left;
}
} else if (val > current.value) {
if (current.right === null) {
current.right = newNode;
return this;
} else {
current = current.right;
}
}
}
}
}
```

That's all the code that we need to perform insertion in a binary search tree.

## Complete Code

This is the complete code for our `BinarySearchTree`

example with `insert`

method using Javascript:

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

So that's it for this article. I hope this article was able to teach you something.

Consider giving a thumbs up and follow me for more blogs. You can also connect with me on Twitter where I keep sharing regular content related to web development, Javascript, and other related stuff.