C program to create a Binary Search Tree | Part1

C program to create a Binary Search Tree | Part1

Question

Write a C program to create a Binary Search Tree. Get the input from the user and create a binary search tree.

What is a Binary Search Tree?

1. The left node is always smaller than its parent.

2. The right node is always greater than its parent.

3. Each node can contain only two child node.

 

binary search tree

 Logic

  • Get the number of elements from the user.
  • For the first input and set as a root of BST.
  • Attach the nodes at the respective positions. In this example, 8 is larger than 5 so it is the right child.  3 is smaller than 5 so it is the left child.
  • After BST is created, it is traverse in PostOrder(Left-Right-Data) fashion. See this to know more about tree traversal.

Program

#include<stdio.h>
/*Node in tree structure*/
struct bst
{
    struct bst* left;   //pointer to left node
    struct bst* right;  //pointer to right node
    int data;
};
void createBST(struct bst** root,int data)
{
    /*Create a temporary node with left and right child as NULL*/
    struct bst* temp =(struct bst*)malloc(sizeof(struct bst));
    temp->data = data;
    temp->left = NULL;
    temp->right = NULL;
    /* pointer used to traverse the tree*/
    struct bst* t = *root;

    /*Create head if first node*/
    if(*root==NULL)
    {
        *root = temp;
        return;
    }
    if(data<t->data)                //given data is smaller than current node
        createBST(&(t->left),data); //traverse along left side
    else                            //given data is larger than current node
        createBST(&(t->right),data); //traverse along right side

}
void traverse(struct bst* root)
{
    if(root!=NULL)
    {
        /*traverse till leftchild is not NULL*/
        traverse(root->left);
        /*traverse till rightchild is not NULL*/
        traverse(root->right);
        /*print data of node*/ 
        printf("%d\n",root->data);
    }
}

int main()
{
    struct bst* root =NULL;
    int i,n,data;
    printf("enter no. of elements");
    scanf("%d",&n);
    /*get n elements from user and create Binary Search Tree*/
    for(i=0;i<n;i++)
    {
        scanf("%d",&data);
        createBST(&root,data);
    }
    traverse(root);                 //Pass the root pointer to traverse the tree
}

You might also like…

To delete a node from the singly linked list.

Follow For Instant Updates

Join WhatsApp Group: link
Join our Telegram Channel: link
Like our Facebook Page:  link
Subscribe to our Youtube channel: link

Sree Hari Sanjeev

The founder of Wisdom Overflow. Software Developer at Zoho Corporation.
0 0 votes
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x