how to add duplicate entries to binary standard tree java

Question

I have written a method that adds non duplicate entries to a bst but now i want to add duplicate nodes to the right child of the original node. I have listed my method on adding non duplicate nodes but i have no clue on how to update my method to add duplicates. Thanks for your help.

private T addEntry(T newEntry) {
    BinaryNodeInterface<T> currentNode = getRootNode();
    assert currentNode != null;
    T result = null;
    boolean found = false;

    while (!found) {
        T currentEntry = currentNode.getData();
        int comparison = newEntry.compareTo(currentEntry);

        if (comparison == 0) { // newEntry matches currentEntry;
                                // return and replace currentEntry
            found = true;
            currentNode.setData(newEntry);
        } else if (comparison < 0) {
            if (currentNode.hasLeftChild())
                currentNode = currentNode.getLeftChild();
            else {
                found = true;
                currentNode.setLeftChild(new BinaryNode<T>(newEntry));
            } // end if
        } else {
            assert comparison > 0;

            if (currentNode.hasRightChild())
                currentNode = currentNode.getRightChild();
            else {
                found = true;
                currentNode.setRightChild(new BinaryNode<T>(newEntry));
            }
        }
    }

    return result;
}

David Coler · Accepted Answer · 2014-12-09 23:22:36Z

1

Take away your comparison here

if (comparison == 0) { // newEntry matches currentEntry;
// return and replace currentEntry
    found = true;
    currentNode.setData(newEntry);

and add a >= to the other comparison

assert comparison >= 0;
        if (currentNode.hasRightChild())
            currentNode = currentNode.getRightChild();
        else {
            found = true;
            currentNode.setRightChild(new BinaryNode<T>(newEntry));
        }

however unless you change the code a bit more the duplicates will wind up at the bottom of the list or the next row down not the right child of the current node. you can do a check to see if they are the same, create a new node setting that to the right child and then set the right child of the new node to the old right child. Doing this however will unbalance the BST.

answered Dec 9, 2014 at 23:22

David Coler

4533 silver badges8 bronze badges

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

Comments

Costi Ciudatu · Accepted Answer · 2014-12-09 23:22:22Z

0

The short answer would be:

Remove the if (comparison == 0) block entirely.
Remove the assert comparison > 0 line

answered Dec 9, 2014 at 23:22

Costi Ciudatu

38.5k7 gold badges58 silver badges95 bronze badges

Collectives™ on Stack Overflow

how to add duplicate entries to binary standard tree java

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related