C programming concepts: Binary Search Tree Insertion

A new key is always inserted in BST as a leaf node.

Non recursive Algorithm

1.Ask key from user.
2.Make root as current node.

If root==NULL                                            //Insert root case
just create root node.
else
    Until current node is not NULL

        1.Keep track of parent of current node.
        2.Search for position of where to insert the key.
        3.If key already exists,return root and stop.(duplicate element case)

    If key is less than parent , insert key as left child.
    else insert as right child.

3.Ask if user wants to insert more keys.If yes goto 1.

4.Return root node.

Code

node* insert(node* root)                           //inserts a node
{
    node* par,*curr;int key;

    do
    {
        printf("\n Enter key ");
        scanf("%d",&key);

        curr=root;

        if(root==NULL)
            root=getnode(key);
        else
        {
            while(curr!=NULL)
            {
                par=curr;

                if(key<curr->key)
                    curr=curr->left;
                else if(key>curr->key)
                    curr=curr->right;
                else
                {
                    printf("\n Trying to insert duplicate data");
                    return root;
                }
            }
            if(key<par->key)
                par->left = getnode(key);
            else
                par->right = getnode(key);
        }

        printf("\n Insert more nodes ? ");
        fflush(stdin);

     }while(getchar()=='y');

     return root;
}

getnode function

node* getnode(int key)                     //creates and returns new node with given key
{
    node* keynode;
    keynode = (node*)malloc(sizeof(node));
    keynode->key=key;
    keynode->left=keynode->right=NULL;
    return keynode;
}