Binary Search Tree in C

Here you will get program for binary search tree in C.

 

A Binary Search Tree (BST) is a binary tree in which all the elements stored in the left subtree of node x are less then x and all elements stored in the right subtree of node x are greater then x. Below I have shared a C program for binary search tree insertion. After inserting all the nodes I am displaying the nodes by preorder traversal (root, left child, right child).

 

Also Read: What are B-Trees?

Program for Binary Search Tree in C

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

typedef struct BST
{
	int data;
	struct BST *left;
	struct BST *right;
}node;

node *create();
void insert(node *,node *);
void preorder(node *);

int main()
{
	char ch;
	node *root=NULL,*temp;
	
	do
	{
		temp=create();
		if(root==NULL)
			root=temp;
		else	
			insert(root,temp);
			
		printf("nDo you want to enter more(y/n)?");
		getchar();
		scanf("%c",&ch);
	}while(ch=='y'|ch=='Y');
	
	printf("nPreorder Traversal: ");
	preorder(root);
	return 0;
}

node *create()
{
	node *temp;
	printf("nEnter data:");
	temp=(node*)malloc(sizeof(node));
	scanf("%d",&temp->data);
	temp->left=temp->right=NULL;
	return temp;
}

void insert(node *root,node *temp)
{
	if(temp->data<root->data)
	{
		if(root->left!=NULL)
			insert(root->left,temp);
		else
			root->left=temp;
	}
	
	if(temp->data>root->data)
	{
		if(root->right!=NULL)
			insert(root->right,temp);
		else
			root->right=temp;
	}
}

void preorder(node *root)
{
	if(root!=NULL)
	{
		printf("%d ",root->data);
		preorder(root->left);
		preorder(root->right);
	}
}
Output
C Program for Binary Search Tree Insertion and Preorder Traversal

Video Tutorial

Comment below if you are facing any problem in this program for binary search tree in C.

8 thoughts on “Binary Search Tree in C”

  1. there is only pre-order traversal,you must have to also define in-order and post-order also deleting node(optional)

    and this program is recursive what about none-recursive program??

    1. hypothetical me

      void postorder(node *root)
      {
      if(root!=NULL)
      {
      postorder(root->left);
      postorder(root->right);
      printf(“%d “,root->data);
      }
      }

  2. I am getting an extra 0 while executing in order and other traversals.m Rest of the elements are in correct order. But why does 0 appear? Please help

  3. Can u plz tell the error in my code
    it is having runtime error
    #include
    #include
    #include
    typedef struct BST
    {
    int data;
    struct BST *left;
    struct BST *right;
    }node;
    node* getnewnode(int x)
    {
    node* temp=(node*)malloc(sizeof(node*));
    temp->data=x;
    temp->left=NULL;
    temp->right=NULL;
    return temp;
    }
    void insert(node* root1,node* temp)
    {

    if(temp->datadata)
    {
    if(root1->left!=NULL)
    {
    insert(root1->left,temp);
    }
    else
    {
    root1->left=temp;
    }
    }
    else if(temp->data>root1->data)
    {
    if(root1->right!=NULL)
    {
    insert(root1->right,temp);
    }
    else
    {
    root1->right=temp;
    }

    }
    }
    bool search(node* rt,int m)
    {
    if(rt==NULL)
    {
    return false;
    }
    else if(rt->data==m)
    {
    return true;
    }
    else if(mdata)
    {
    return search(rt->left,m);
    }
    else
    {
    return search(rt->right,m);
    }
    }
    void pretrav(node* tree)
    {
    if(tree!=NULL)
    {
    printf(“%d\t”,tree->data);
    pretrav(tree->left);
    pretrav(tree->right);
    }
    }
    void posttrav(node* tree)
    {
    if(tree!=NULL)
    {
    posttrav(tree->left);
    posttrav(tree->right);
    printf(“%d “,tree->data);
    }
    }
    void intrav(node* tree)
    {
    if(tree!=NULL)
    {
    intrav(tree->left);
    printf(“%d”,tree->data);
    intrav(tree->right);
    }
    }
    int main()
    {
    node* root,*temp;
    root=NULL;
    int x,num,c;
    char ch;
    do
    {
    printf(“BINARY SEARCH TREE\n”);
    printf(“Press 1 to create the tree\n”);
    printf(“Press 2 to search node \n”);
    printf(“Press 3 to print prefix notation or preorder traversal\n”);
    printf(“Press 4 to extract post order traversal:\n”);
    printf(“Press 5 to print inorder traversal:\n”);
    printf(“Press 6 to exit\n”);
    scanf(“%d”,&c);
    switch(c)
    {
    case 1 :
    do
    {
    printf(“Enter the data”);
    scanf(“%d”,&x);
    temp=getnewnode(x);
    if(root==NULL)
    root=temp;
    else
    insert(root,temp);
    printf(“nDo you want to enter more(y/n)?”);
    getchar();
    scanf(“%c”,&ch);
    }while(ch==’y’|ch==’Y’);

    printf(“Elements have been entered \n”);
    break;
    case 2 : printf(“Enter the number to be searched \n”);
    scanf(“%d”,&num);
    if(search(root,num)==true)
    {
    printf(“Number Found \n”);
    }
    else
    {
    printf(“Number not found \n”);
    }
    break;
    case 3 : printf(“Pre-Order Traversal is:\n”);
    pretrav(root);
    break;
    case 4 : printf(“Post-Order Traversal is:\n”);
    posttrav(root);
    break;
    case 5 : printf(“In-Order Traversal is :\n”);
    intrav(root);
    break;
    }
    }while(c!=6);
    }

Leave a Comment

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