2

I'm working with BST at the moment and I'm having a few problems with my insertion method although it seems quite logical to me. After debugging, I found out that there's a problem with the assignment of the variables I used, like every time I try to insert a node, it gets inserted as a root and therefore it prints out, "duplicates not allowed" .

For this , I'm working with 4 classes respectively. The following method is in the BinarySearchTree class that extends the BinaryTree class. In the binary tree class I have a protected BinaryTreeNode and other methods for the tree traversals.

Method call from the Main :

    int value;
    System.out.println("Number of elements to be inserted: ");
    value = input.nextInt();

    for (int i = 0; i < value; i++) {
        System.out.print("Enter next element ");
        num = console.nextInt();
        x.setNum(num);

        tree.insert(x);
    }

Problem was with the method call in the main method and not the inset itself.

Improve this question
12
  • Where do you call insert? Are you actually inserting two different DataElement objects? Commented Jan 10, 2014 at 17:01
  • @crush insert is called in the main method, I'm having a for loop that asks the user to insert different values that get inserted in the tree. And I'm inserting 1 DataElement actually. Commented Jan 10, 2014 at 17:02
  • Can we see that method, please? Commented Jan 10, 2014 at 17:03
  • What do you consider a duplicate? A reference to the same object, or two objects that have the same values? Commented Jan 10, 2014 at 17:07
  • Well, I'm trying ti insert different values to the tree, when I insert the very first one, it's not a problem, but as I start inserting the rest it prints out the duplicates message. By the duplicates I mean that in the tree, no 2 nodes can have the same value Commented Jan 10, 2014 at 17:10

2 Answers 2

Reset to default
1

The problem is in a couple of places. Let's start with your main() method.

for (int i = 1; i <= numElt; i++) {
    System.out.print("Enter next element ");
    num = input.nextInt();
    x.setNum(num);

    tree.insert(x);
}

As you loop through the elements, you are simply changing the value of a single DataElement object (x).

When you insert this DataElement object to your BST, you create a new BinaryTreeNode, and then set a reference to this DataElement object.

BinaryTreeNode node = new BinaryTreeNode();
node.info = insertItem; //Reference set to the object here.

Now, ignore the rest of the insert method for a second, and go back to your loop. On the next iteration, you are changing the value of the DataElement object.

But the BinaryTreeNode you just inserted holds a reference to that same DataElement object. So, when you change the value in the new iteration, the last BinaryTreeNode sees the change too.

Instead, you need to create a new DataElement on each iteration of the loop, and pass that to the insert() method.

So,

for (int i = 1; i <= numElt; i++) {
    x = new DataElement(...); //... means whatever constructor parameters it takes.
    System.out.print("Enter next element ");
    num = input.nextInt();
    x.setNum(num);

    tree.insert(x);
}

This will give each BinaryTreeNode it's own object instance of DataElement.

Detecting Duplicates

Wait, there's more. You defined duplicates as objects with the same value, not same reference. So there is more work to be done.

Here, in your insert method, you check if the insertItem is the same reference as the last node.

if (temp.info == insertItem) {
    System.out.println("We can't have duplicates!");
    return;
}

If you want to compare them by value, you should use the equals method:

if (temp.info.equals(insertItem))

This should check them by value, instead of by reference.

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

wow, this makes a lot of sense! So you're implying that I create a new DataElement within the loop to avoid referring to the same DataElement object?
@Sara Yes, exactly. Also, don't forget to compare the DataElement objects by value with equals or you won't detect duplicates.
@Sara It looks like you could use that compareTo method to check values as well, except check != 0 instead of > 0 or < 0.
The compareTo is used to help in traversal, like whether to go through the left or the right part of the tree
the really helps a lot! Thank you!
|
1

Try changing

if (temp.info == insertItem)

to

if (temp.info.equals(insertItem))

or

if (temp.info.compareTo(insertItem) == 0)

Improve this answer

3 Comments

If temp.info == insertItem, then they are a reference to the same object, thus "duplicates".
That won't make a difference, because that actually means the same thing.
@Sara it doesn't mean the same thing. The first block compares the object reference. The second block compares their values. However, since you are setting the references, and reusing the same object, they will always have the same values too.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.