# Insertion In A Binary Search Tree In C++

## Insertion In A Binary Search Tree

A binary search tree is a tree in which the data in left subtree is less than the root and the data in right subtree is greater than the root. In this article, insertion is performed using recursion in C++.

## Rules For Binary Search Tree:

• Left subtree for any given node will only contain nodes which are lesser than the current node
• Right subtree for any given node will only contain nodes which are greater than the current node
• This is valid for all nodes present in BST.

## Algorithm To Insert In BST:

1. Input the value of the element to be inserted.
2. Start from the root.
3. If the input element is less than current node, recurse for left subtree otherwise for right subtree.
4. Insert the node wherever NULL is encountered.

## Code:

#include <bits/stdc++.h>
using namespace std;
class Tree {
public:
int data;
Tree* left = NULL,*right = NULL;
// Constructor initialised
Tree(int x) {
data = x;
left = NULL;
right = NULL;
}
};
void inorder_traversal (Tree *root) {
if (root == NULLreturn;
// Visit Left subtree
inorder_traversal(root -> left);
// Print the data
cout << root -> data << ” “;
// Visit right subtree
inorder_traversal(root -> right);

}
Tree* insert_node(Tree* rootint x) {
// If leaf is encountered
if (root == NULL) {
Tree *temp = new Tree(x);
return temp;
}
// Recur for left subtree
if (root -> data > x) {
root -> left = insert_node(root -> left, x);
}
// Recur for right subtree
else {
root -> right = insert_node(root -> right , x);
}
return root;

}
int main() {
Tree *root = new Tree(15);
root -> left = new Tree(12);
root -> right = new Tree(54);
root -> left -> left = new Tree(8);
root -> left -> right = new Tree(13);
root -> left -> left -> left = new Tree(5);
root -> right -> left = new Tree(20);
int x = 10;
insert_node(root, x);
cout << “Inorder Traversal – “;
inorder_traversal(root);
return 0;
}

## Output:

Inorder Traversal - 5 8 10 12 13 15 20 54

O(n)

O(h)