CODEWITHSUNDEEP
javabinary-search-tree
user4021279
user4021279

Reputation: 13

how to add duplicate entries to binary standard tree java

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

Upvotes: 1

Views: 320

Answers (2)

David Coler
David Coler

Reputation: 453

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.

Upvotes: 1

Costi Ciudatu
Costi Ciudatu

Reputation: 38195

The short answer would be:

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

Upvotes: 0

Related Questions