## How would you insert an element into a Binary Search Tree?

Insertion into a Binary Search Tree will happen using the rule of L<N<R. You would compare the new element with the root and based on it being greater or smaller than the root value it goes to right or left. If the new element is equal to the root value then it goes to the right side. This will continue till the element doesn't have an element greater than or smaller than itself.
The same is explained in the pseudo code below. You can execute this iteratively or recursively.

```
node=root
if (element.value>=node.value){
if (node.right==null){
} else{
//redo the logic with node=node.right
}
}
else{
if (node.left==null){
} else{
//redo the logic with node=node.left
}
}```

To represent the following BST and do insertions you can go through the example

Definition of the TreeNode class

```
class TreeNode{
int value;
TreeNode left;
TreeNode right;

public static boolean insert(TreeNode root, TreeNode n){
if (n!=null){
if (n.value>=root.value){
if (root.right==null){
root.right=n;
return true;
}
else{
return insert(root.right,n);
}
}
else{
if (root.left==null){
root.left=n;
return true;
}
else{
return insert(root.left,n);
}
}
}
return false;
}

public TreeNode(int x){
value=x;
}
}```

Test code for the insertion.

```
public class BSTUtil {
public static void main(String[] args) {
TreeNode root=new TreeNode(8);
TreeNode.insert(root, new TreeNode(3));
TreeNode.insert(root, new TreeNode(10));
TreeNode.insert(root, new TreeNode(6));
TreeNode.insert(root, new TreeNode(1));
TreeNode.insert(root, new TreeNode(14));
TreeNode.insert(root, new TreeNode(4));
TreeNode.insert(root, new TreeNode(7));
TreeNode.insert(root, new TreeNode(13));
}
}```

This will result in the BST mentioned in the diagram

core java 12