BSTD inorder traversal produces erroneous behaviour

Question

I have a BSTD implementation which is inserting values incorrectly and I can't find for the life of me what is going on.

  EXPECTED ACTUAL  
  -------- ---------- 
  Alex     Janice    
  Carlos   Janice    
  Elton    Janice    
  Janice   Zidane    
  Zidane   Zidane  

Implementation

private Node<K,E> insert(Node<K,E> node, K key, E elem) {

    if (node == null) {
        return new Node<K,E>(null, key, elem, null);
    }

    if (key.compareTo(node.getKey()) < 0) {
        return new Node<K, E>(insert(node.getLeft(), key, elem), key, elem, node.getRight());
    }
    else if (node.getKey().equals(key)) {
        return node;
    }
    else {
        return new Node<K, E>(node.getLeft(), key, elem, insert(node.getRight(), key, elem));
    }
}

I've tried debugging this for over an hour with no luck, any ideas where is my recursion going wrong?

Answer 1

It is the new node, that should take its content from node in general.

It must be the equals/compare. More solid code would be:

int comparison = key.compareTo(node.getKey());
if (comparison < 0) {
    return new Node<K, E>(
        insert(node.getLeft(), key, elem),
        node.getKey(), node.getElem(),
        node.getRight());
}
else if (comparison == 0) {
    return node;
}
else {
    return new Node<K, E>(
        node.getLeft(),
        node.getKey(), node.getElem(),
        insert(node.getRight(), key, elem));
}

This relies only on compareTo.