Adding duplicate numbers to a binary search tree-CodePudding

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.

#include <stdio.h>
#include <stdlib.h>

typedef struct tree{
    int data;
    struct tree *left;
    struct tree *right;
} tree;

tree *new(int num){
    tree *temp = (struct tree *)(malloc(sizeof(tree)));

    temp->data = num;
    temp->left = NULL;
    temp->right = NULL;

    return temp;
}

tree *copy(tree *root){
    if(root == NULL){
        return NULL;
    }

    tree *newnode = new(root->data);
    
    newnode->left = copy(root->left);
    newnode->right = copy(root->right);

    return newnode;
}


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;
}

void print(tree *root){
    if(root == NULL){
        return;
    }
    print(root->left);
    printf("%d ", root->data);
    print(root->right);
}

int main(){

    tree *root = NULL;

    root = insert(root, 5);
    root = insert(root, 3);
    root = insert(root, 6);
    root = insert(root, 9);
    root = insert(root, 2);
    root = insert(root, 1);
    root = insert(root, 3);

    print(root);

}

Thank you for helping out!

sidenote: I also tried a version of the insert function like this, without the copy function.

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 = tree->left;
            
            tree->left->data = data;

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

    return tree;
}

But this version turned every number after the duplicate into that number like this:

            5
          /   \
         3     6
        / \     \
       3   4     9
      /
     3
    /
   3

CodePudding user response：

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 :)