Monday, 13 March 2017

C++ Program to insert a Node in Binary Search Tree (BST)

This question has been appeared in the interview of following companies:
Amazon, Microsoft

Source: geeksforgeeks

A binary search tree is also known as sorted tree and ordered tree. In Binary Seach Tree every node has at most two children nodes (a left and a right child). Each node has an integer written inside it. If the number X is written inside a node, then the numbers in its left subtree are less than X and the numbers in its right subtree are greater than X.

Example:
                                                         2
                                                       /    \
                                                     /        \
                                                   1           5
                                                              /    \
                                                            /        \
                                                          3           6
                            
                           preorder traversal of the above BST is: 2 1 5 3 6


Inserting a Node in BST:

Let's assume we have to insert a node  in the BST , where node->data=4

Algorithm:
    


1. Let x be the element you want to insert in BST:
2. Pass the root node and element x to the insert method.
2. Let insert(temp,x)  be the method which is called to insert the node.
3. Check If temp=NULL:
4.                  temp.data=x
5.                  temp.left=NULL
6.                  temp.right=NULL
7.         If temp->data>element:
8.                  temp.left=insert(temp->left,x)
9.                          ///continue invoking method for checking the
10.                            elements of left subtree till of the temp
11.                            node
12.         If temp->data<element:
13.                 temp.right=insert(temp->right,x)
14.                         ///continue invoking method for checking the
15.                            elements of left subtree till of the temp
16.                            node
 


PROGRAM:

#include <stdio.h>
#include <stdlib.h>
struct node
{
   int data;
   struct node *left,*right;
}*root=NULL;
void create_bst();
node* insert(struct node *temp,int data);
void inorder(struct node *temp);
int main()
{
       int element;
    create_bst();
    printf("\n\nPreorder traversal of BST: \n");
    inorder(root);
    printf("\nEnter the element you want to insert in the BST: ");
    scanf("%d",&element);
    insert(root,element);
    printf("\n\nPreorder traversal of BST after inserting node: \n");
    inorder(root);
    return 0;
}
void create_bst()
{
    root=(struct node*)malloc(sizeof(struct node));
    root->data=2;
    root->left=(struct node*)malloc(sizeof(struct node));
    root->left->data=1;
       root->left->left=root->left->right=NULL;

       root->right=(struct node*)malloc(sizeof(struct node));
       root->right->data=5;
       root->right->left=(struct node*)malloc(sizeof(struct node));
       root->right->left->data=3;
       root->right->left->left=root->right->left->right=NULL;
       root->right->right=(struct node*)malloc(sizeof(struct node));
       root->right->right->data=6;
       root->right->right->left=root->right->right->right=NULL;
}
node* insert(struct node *temp,int element)
{
    if(temp==NULL)
    {
              temp=(struct node*)malloc(sizeof(struct node));
              temp->data=element;
              temp->right=temp->left=NULL;
              return temp;
    }
    if(element<temp->data)
    {
           temp->left=insert(temp->left,element);
    }
    if(element>temp->data)
    {
           temp->right=insert(temp->right,element);
    }
    return temp;
}
void inorder(struct node *temp)
{
    if(root==NULL)
    {
           return;
    }
    printf("%d ",temp->data);
    if(temp->left!=NULL)
    {
           inorder(temp->left);
    }
    if(temp->right!=NULL)
    {
           inorder(temp->right);
    }
}

OUTPUT:
 


EmoticonEmoticon