printf prints text two times in while loop even after fflushing stdin after scanf

Question

So, this is the code, it takes input, inserts/sorts depending on choice, now the problem is in the input part, Somehow getchar misses a cycle every time. I know this is related to stdin and ENTER but I tried flushing it, I still got the same bad output.

#include <stdio.h>
#include <stdlib.h>
struct nd{
    int data;
    struct nd *right;
    struct nd *left;
};

typedef struct nd NODE;
void insert(NODE **, int);
void traverse(NODE *);

void insert(NODE **root,int data){
    if(*root==NULL){
        *root=(NODE*)malloc(sizeof(NODE));
        if(*root==NULL){
            puts("Memory can't be allocated for root node.");
            return;
        }
        (**root).data=data;
        (**root).left=NULL;
        (**root).right=NULL;
        puts("root node allocation was successful.");
        return;
    }
    NODE *current=*root;
    NODE *parent;
    while(1){
        parent=current;
        current=data>=(*current).data?(*current).right:(*current).left;
        if(current==NULL){
            current=(NODE*)malloc(sizeof(NODE));
            if(current==NULL){
                puts("Memory can't be allocated for node.");
                return;
            }
            (*current).data=data;
            (*current).right=NULL;
            (*current).left=NULL;
            int isRight=data>=(*parent).data;
            if(isRight){
                (*parent).right=current;
            }
            else{
                (*parent).left=current;
            }
            puts("\nValue inserted successfully.");
            return;
        }
    }
}
void traverse(NODE *root){    /*This is the krabby patty formula*/
    if(root!=NULL){
    traverse((*root).left);   
    printf("%d\t",(*root).data);
    traverse((*root).right);
    }
}
int main(void){
    NODE *root=NULL;
    int data;
    while(1){
        printf("Insert or sort?(I/S): ");
        char ch=getchar();
        if(ch=='I'){
            printf("\nEnter data: ");
            scanf("%d",&data);
            fflush(stdin);
            insert(&root,data);
        }
        if(ch=='S'){
            traverse(root);
            puts("\n");
        }
    }
}

Now, when I execute this, I get the output:

Insert or sort?(I/S): I

Enter data: 23
root node allocation was successful.
Insert or sort?(I/S): Insert or sort?(I/S): I

Enter data: -2

Value inserted successfully.
Insert or sort?(I/S): Insert or sort?(I/S): I

Enter data: 39

Value inserted successfully.
Insert or sort?(I/S): Insert or sort?(I/S): S
-2  23  39  

Insert or sort?(I/S): Insert or sort?(I/S): 

Everything works as expected except the printf statement, my guess is that there was an ENTER left in stdin, but I flushed it, so that should have solved the problem, but it didn't. How do I make this go away?