How to print if the value inserted in a BST should be inserted in the left or right subtree

Question

I'm inserting values in a BST and printing "left" if the value should be inserted in the left subtree or "right" if the value should be inserted in the right subtree but when I'm going to print, several right/left are printed, how can I fix it? I think it's due to recursion but I can't solve it without recursion.

BST insertion code:

Node *insert(Node **root, int key)
{
    if(*root == NULL)
    {
        Node *newNode = (Node*)malloc(sizeof(Node));
        if(newNode == NULL)
            return NULL;
        newNode->key= key;
        newNode->left = NULL;
        newNode->right = NULL;
        (*root) = newNode; 
        return newNode; 
    }
    if(key < (*root)->key){
        printf("left ");
        return insert(&((*root)->left),key);
    }
    else{
        printf("right ");
        return insert((&(*root)->right),key);
    }
}

Example: Inserting the values: 25 - 20 - 36 - 10 - 22 - 30

Answer 1

What I have got from the expected output is that the "left" or "right" indicates the relative position of the node with respect to its parent node. If this is so, you can do this:

if(key < (*root)->key){
    if ( (*root)->left==NULL)
        printf("left ");
    return insert(&((*root)->left),key);
}
else{
    if ( (*root)->right==NULL)
           printf("right ");
    return insert((&(*root)->right),key);
}

The logic is, We will get to know whether it is left or right just 1 step before the insertion step. I just checked if the next node we are going to , is NULL or not.