#### Tree

Problem
Implement an algorithm to insert a node in a Binary Search Tree ( BST ).

Solution
We need to follow the properties of Binary Search Tree ( BST ) to insert a node at an appropriate place in the tree. We use a recursive algorithm to traverse through different subtrees by comparing the value of the parent node ( P ) and the value of the node to be inserted ( N ). For e.g, if N -> data < P -> data , the new node will be inserted in the left subtree of P . So, we move to the left subtree and follow the same step. This process continues till we reach a node with 0 or 1 child where we can insert the new node.
Following figure illustrates how nodes are inserted in a BST :

```#include<iostream>
using namespace std;

// node structure
typedef struct tree_node {
int value;
struct tree_node *left, *right;
}node;

// create a new node
node *getNewNode(int value) {
node *new_node = new node;
new_node->value = value;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}

// inorder traversal of a tree
void inorderTraversal(node *ptr) {
if(ptr == NULL)
return;
else {
inorderTraversal(ptr->left);
cout<<ptr->value<<"\t";
inorderTraversal(ptr->right);
}
}

// Node Insertion
node *insertNode(node *ptr,int data) {
if (ptr == NULL)
return getNewNode(data);
if (data <= ptr->value) // node will be inserted in left subtree
ptr->left = insertNode(ptr->left,data);
else // node will be inserted in right subtree
ptr->right = insertNode(ptr->right,data);
return ptr;
}

// main
int main() {
node *root = NULL;
root = insertNode(root,31);
insertNode(root,16);
insertNode(root,45);
insertNode(root,24);
insertNode(root,7);
insertNode(root,19);
insertNode(root,29);
cout<<"\nInorder traversal :-\n";
inorderTraversal(root);
cout<<endl;
return 0;
}```