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:

---

[wpusb]