# Binary search tree operations with Program

There are Six operation which we can perform on Binary search Tree.

## Binary search tree operations

### Search

Searches an element in a tree.

### Insert

Inserts an element in a tree.

### Pre order Traversal

Traverse a tree in a pre-order manner means first to traverse the Root node, then the Left node, and at last Right node.

Traverse format : (Root, Left, Right)

### Pre order Traversal Program in C

```#include<stdio.h>
#include<stdlib.h>

struct node{
int key;
struct node *left;
struct node *right;
};

struct node *createNode(int item)
{
struct node *newNode =  (struct node *)malloc(sizeof(struct node));
newNode->key = item;
newNode->left = newNode->right = NULL;
return newNode;
}

struct node *insertNode(struct node* node, int key)
{
if (node == NULL) return createNode(key);
if (key < node->key)
node->left  = insertNode(node->left, key);
else if (key > node->key)
node->right = insertNode(node->right, key);
return node;
}

struct node* search(struct node* root, int key)
{
if (root == NULL || root->key == key)
return root;

if (root->key < key)
return search(root->right, key);

return search(root->left, key);
}

void preOrder(struct node *root)
{
if (root != NULL)
{
printf("%d \n", root->key);
preOrder(root->left);
preOrder(root->right);
}
}

int main()
{
struct node *root = NULL;
root = insertNode(root, 50);
insertNode(root, 30);
insertNode(root, 20);
insertNode(root, 40);
insertNode(root, 70);
insertNode(root, 60);
insertNode(root, 80);
printf("Pre-Order Tree Traversal\n");
preOrder(root);
return 0;
}
```

### In order Traversal

Traverse a tree in an in-order manner means first to traverse the Left node, then the root node, and then at last Right node.

Traverse format : (Left, Root, Right)

### In order Traversal Program in C

```#include<stdio.h>
#include<stdlib.h>

struct node{
int key;
struct node *left;
struct node *right;
};

struct node *createNode(int item)
{
struct node *newNode =  (struct node *)malloc(sizeof(struct node));
newNode->key = item;
newNode->left = newNode->right = NULL;
return newNode;
}

struct node *insertNode(struct node* node, int key)
{
if (node == NULL) return createNode(key);
if (key < node->key)
node->left  = insertNode(node->left, key);
else if (key > node->key)
node->right = insertNode(node->right, key);
return node;
}

void inOrder(struct node *root)
{
if (root != NULL)
{
inOrder(root->left);
printf("%d \n", root->key);
inOrder(root->right);
}
}
int main()
{
struct node *root = NULL;
root = insertNode(root, 50);
insertNode(root, 30);
insertNode(root, 20);
insertNode(root, 40);
insertNode(root, 70);
insertNode(root, 60);
insertNode(root, 80);
printf("In-Order Tree Traversal\n");
inOrder(root);
return 0;
}
```

### Post-order Traversal

Traverse a tree in a post-order manner means the first traverse left node, then the right node, and the last root node.

Traverse format : (Left, Right, Root)

```#include<stdio.h>
#include<stdlib.h>

struct node{
int key;
struct node *left;
struct node *right;
};

struct node *createNode(int item)
{
struct node *newNode =  (struct node *)malloc(sizeof(struct node));
newNode->key = item;
newNode->left = newNode->right = NULL;
return newNode;
}

struct node *insertNode(struct node* node, int key)
{
if (node == NULL) return createNode(key);
if (key < node->key)
node->left  = insertNode(node->left, key);
else if (key > node->key)
node->right = insertNode(node->right, key);
return node;
}

struct node* search(struct node* root, int key)
{
if (root == NULL || root->key == key)
return root;

if (root->key < key)
return search(root->right, key);

return search(root->left, key);
}

void postOrder(struct node *root)
{
if (root != NULL)
{
postOrder(root->left);
postOrder(root->right);
printf("%d \n", root->key);
}
}

int main()
{
struct node *root = NULL;
root = insertNode(root, 50);
insertNode(root, 30);
insertNode(root, 20);
insertNode(root, 40);
insertNode(root, 70);
insertNode(root, 60);
insertNode(root, 80);
printf("Post-Order Tree Traversal\n");
postOrder(root);
return 0;
}
```

## C Program to implement Insertion and searching in binary search tree

```#include<stdio.h>
#include<stdlib.h>

struct node{
int key;
struct node *left;
struct node *right;
};

struct node *createNode(int item)
{
struct node *newNode =  (struct node *)malloc(sizeof(struct node));
newNode->key = item;
newNode->left = newNode->right = NULL;
return newNode;
}

struct node *insertNode(struct node* node, int key)
{
if (node == NULL) return createNode(key);
if (key < node->key)
node->left  = insertNode(node->left, key);
else if (key > node->key)
node->right = insertNode(node->right, key);
return node;
}

struct node* search(struct node* root, int key)
{
if (root == NULL || root->key == key)
return root;

if (root->key < key)
return search(root->right, key);

return search(root->left, key);
}

int main()
{
struct node *root = NULL;
root = insertNode(root, 60);
insertNode(root, 30);
insertNode(root, 20);
insertNode(root, 50);
insertNode(root, 70);
insertNode(root, 90);
insertNode(root, 80);
struct node *result = search(root, 90);
printf("Search Value %d is founded",result->key);
return 0;
}
```

Output: