Binary Search Tree – All operations

Binary Search Tree


                                               
Implement a C program to construct a Binary Search Tree and also display the elements in the tree using Inorder , Preorder and Postorder traversals.

Create a structure

 struct tnode
{
 int data;
 struct tnode * leftc;
 struct tnode * rightc;
};

Binary Search tree is a binary tree in which each internal node x stores an element such that the element stored in the left subtree of x are less than or equal to x and elements stored in the right subtree of x are greater than or equal to x. This is called binary-search-tree property.
Input and Output Format:
Refer Sample Input and Output for formatting specifications.
[All text in bold corresponds to input and the rest corresponds to output]
Sample Input and Output:
Enter the element to be inserted in the tree
1
Do you want to insert another element?
yes
Enter the element to be inserted in the tree
2
Do you want to insert another element?
yes
Enter the element to be inserted in the tree
3
Do you want to insert another element?
yes
Enter the element to be inserted in the tree
4
Do you want to insert another element?
no
Inorder Traversal : The elements in the tree are 1 2 3 4
Preorder Traversal : The elements in the tree are 1 2 3 4
Postorder Traversal : The elements in the tree are 4 3 2 1


Code:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct tnode {
          int data;
          struct tnode * leftc;
          struct tnode * rightc;
};
void insert(struct tnode **, int num);
void inorder(struct tnode *);
void preorder(struct tnode *);
void postorder(struct tnode *);
int main() {
          struct tnode * root=NULL;
          char ch[5];
          int num;
          do  {
                   printf(“Enter the element to be inserted in the treen”);
                   scanf(“%d”,&num);
                   insert(&root, num);
                   printf(“Do you want to insert another element?n”);
                   scanf(“%s”,ch);
          }while(strcmp(ch,”yes”)==0);
          printf(“Inorder Traversal : The elements in the tree are”);
          inorder(root);
          printf(“n”);
          printf(“Preorder Traversal : The elements in the tree are”);
          preorder(root);
          printf(“n”);
          printf(“Postorder Traversal : The elements in the tree are”);
          postorder(root);
          printf(“n”);
          return 0;
}
void insert(struct tnode ** s, int num) {
    if(*s==NULL)
    {
        (*s)=(struct tnode *)malloc(sizeof(struct tnode));
        (*s)->data=num;
        (*s)->leftc=NULL;
        (*s)->rightc=NULL;
    }
    else
    {
        if((*s)->data>num)
            insert(&(*s)->leftc,num);
        else
            insert(&(*s)->rightc,num);
    }
   
}
void inorder(struct tnode * s)  {
    if(s==NULL)
        return;
    else
    {
        inorder(s->leftc);
        printf(” %d”,s->data);
        inorder(s->rightc);
    }
}
void preorder(struct tnode * s) {
    if(s==NULL)
        return;
    else
    {
        printf(” %d”,s->data);
        preorder(s->leftc);
        preorder(s->rightc);
    }
}
void postorder(struct tnode * s) {
    if(s==NULL)
        return;
    else
    {
        postorder(s->leftc);
        postorder(s->rightc);
        printf(” %d”,s->data);
    }
}
Search Operation:
int search(struct tnode * s, int ele) {
    if(s==NULL)
        return 0;
    else
    {   if(ele==s->data)
            return 1;
        else if(ele< s->data)
            return search(s->leftc,ele);
        else
            return search(s->rightc,ele);
     
    }
}
Find the size of the tree:
int findSize(struct tnode * s) {
    if(s==NULL)
        return 0;
    else
    return(findSize(s->leftc)+findSize(s->rightc)+1);
}

Finding maximum depth:
 int findMaxDepth(struct tnode * s) {
       if(s==NULL)
            return 0;
        else
            {
                int left=findMaxDepth(s->leftc);
                int right=findMaxDepth(s->rightc);
                if(left>right)
                    return (left+1);
                else
                    return (right+1);
            }

}

Please do comment If u have any Queries!

Add a Comment

Your email address will not be published. Required fields are marked *