**Data Structure: Binary Search Tree implementation with in-order traversing**

*A binary search tree is a binary tree where each node has a Comparable data and satisfies the restriction that the data in any node is larger than the data's in all nodes in that node's left subtree and smaller than the data's in all nodes in that node's right subtree.*

**Basic Operations performed on Binary Search Trees:***1. Search − Searches an element in a Binary Search Trees.*

2. Insert − Inserts an element in a Binary Search Trees.

2. Insert − Inserts an element in a Binary Search Trees.

3. Pre-order Traversal − Traverses a tree in a pre-order manner form the Binary Search Trees.

3. Pre-order Traversal − Traverses a tree in a pre-order manner form the Binary Search Trees.

4. In-order Traversal − Traverses a tree in an in-order manner from the Binary Search Trees.

4. In-order Traversal − Traverses a tree in an in-order manner from the Binary Search Trees.

5. Post-order Traversal − Traverses a tree in a post-order manner from the Binary Search Trees.

5. Post-order Traversal − Traverses a tree in a post-order manner from the Binary Search Trees.

**Implementation of the Binary Search Tree in C++ language:***we define a node structure having some info part, the pointer to its left child and right child nodes. We simply create this node with the help of structure.*

**Node Structure of a Binary Search Tree:***struct node*

{

int info;

node *left;

node *right;

};

{

int info;

node *left;

node *right;

};

*Whenever an element is to be inserted, first locate its proper location. Start searching from the root node, then if the data is less than the key value, search for the empty location in the left subtree and insert the data. Otherwise, search for the empty location in the right subtree and insert the data.*

**Insert Operation in Binary Search tree:**node * createBST( node *r, int val)

{

if(r==NULL)

{

r=new node;

r->info=val;

r->left=NULL;

r->right=NULL;

}

else if(val<=r->info)

{

r->left=createBST(r->left,val);

}

else

{

r->right=createBST(r->right,val);

}

return r;

}

*In this function, we write a code to traverse the node of the Binary search tree in the In-order way. The rules for In-order traversing is First we write left-child -> root-node -> right-child.*

**In-order Traversing function of Binary Search Tree:**
void inOrder( node *r)

{

if(r!=NULL)

{

total++;

if(r->left==NULL && r->right==NULL)

ext++;

inOrder(r->left);

cout<<r->info<<" ";

inOrder(r->right);

}

}

{

if(r!=NULL)

{

total++;

if(r->left==NULL && r->right==NULL)

ext++;

inOrder(r->left);

cout<<r->info<<" ";

inOrder(r->right);

}

}

**Main function of implemention Binary search Tree:**int main()

{

node *r=NULL;

int n,val;

cin>>n;

for(int i=0;i<n;i++)

{

cin>>val;

r=createBST(r,val);

}

cout<<"Inorder"<<endl;

inOrder(r);

cout<<endl;

cout<<"total nodes="<<total<<endl<<"external nodes:"<<ext<<endl<<"internal nodes:"<<total-ext<<endl;

}

**Thanks**

**Mukesh Rajput**
## Post A Comment:

## 0 comments:

Thanks

Mukesh Rajput