Adding duplicate numbers to a binary search tree

Question

So I am trying to make a function for a binary search tree where if you input a number that already exists, the number gets added to the left child and the left subtree gets pushed down one step.

To visualize this

if we have a tree that looks like

        5
      /   \
     3     6
    / \     \
   2   4     9
  /
 1

And insert a 3 into here, the tree becomes

            5
          /   \
         3     6
        /       \
       3         9
      / \
     2   4
    /
   1

But what happens in my code is that every number after the duplicate gets inserted twice so that the result becomes

                5
              /   \
             3     6
            / \     \
           3   4     9
          /
         2
        /
       2
      /
     1
    /
   1

Below is the code I have so far.

tree *insert(tree *tree, int data){
    if(tree == NULL){
        return new(data);
    }

    if(data > tree->data){
        tree->right = insert(tree->right, data);
    }
    else if(data < tree->data){
        tree->left = insert(tree->left, data);
    }
    else if(data == tree->data){
        if(tree->left == NULL){
            tree->left = insert(tree->left, data);
        }
        else if(tree->left != NULL){
            struct tree *temp = copy(tree->left);

            
            tree->left->data = data;

            tree->left->left = insert(temp, temp->data);
        }
    }

    return tree;
}

Thank you for helping out!

Answer 1

Try the following version of the insert function. I have added comments for your convenience. Hopefully, you will understand.

tree *insert(tree *tree, int data){
    if(tree == NULL){
        return new(data);
    }

    if(data > tree->data){
        tree->right = insert(tree->right, data);
    }
    else if(data < tree->data){
        tree->left = insert(tree->left, data);
    }
    else if(data == tree->data){
        if(tree->left == NULL){
            tree->left = insert(tree->left, data);
        }
        else if(tree->left != NULL){
            struct tree *temp = copy(tree->left);
            struct tree *newNode = new(data); // creating new node with the data
            newNode->left = temp; // newNode's left will point to the copied left tree
            tree->left = newNode; // and tree left will now points to newNode
        }
    }

    return tree;
}

Let me know if it works. Happy coding :)