create binary tree that does not accept duplicates

Question

I'm trying to make a binary tree that does not accept duplicates ironically I've been able to do the opposite:

public void insertLeaf(String a){
    Node newNode = new Node(a);
    if(node==null){
        node=newNode;
        return;
    }
    Node currentValue = node;
    Node parent = null;
    while(true){
        parent = currentValue;
        if(a.compareTo(currentValue.data)<0){               
            currentValue = currentValue.left;

            if(currentValue==null ){
                parent.left = newNode;
                return;
            }
        }else{
            currentValue = currentValue.right;
            if(currentValue==null){
                parent.right = newNode;
                return;
            }
        }   
    }
}

Heres the Node class

class Node{
    String data;
    Node left;
    Node right; 
    public Node(String data){
        this.data = data;
        left = null;
        right = null;
    }
}

Thanks for your help.

How do you expect to handle duplicates differently when your code does not have any special processing for the case when `compareTo` returns zero? — Sergey Kalinichenko, Aug 09 '16 at 11:56
Possible duplicate of [What is a debugger and how can it help me diagnose problems?](http://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — Jiri Tousek, Aug 09 '16 at 12:01

score 2 · Accepted Answer · answered Aug 09 '16 at 11:57

The problem is your else clause - it accepts both the cases of a.compareTo(currentValue.data)>0 and a.compareTo(currentValue.data)==0. It should only accept the former. When a.compareTo(currentValue.data)==0, you shouldn't add the value to the tree.

Your condition should be :

    if(a.compareTo(currentValue.data)<0){               
        currentValue = currentValue.left;
        if(currentValue==null ){
            parent.left = newNode;
            return;
        }
    } else if (a.compareTo(currentValue.data)>0) {
        currentValue = currentValue.right;
        if(currentValue==null){
            parent.right = newNode;
            return;
        }
    } else {
        return; // don't add the a duplicate value
    }

create binary tree that does not accept duplicates

1 Answers1