Binary Search Tree insert method (map interface)

Question

This is my implementation based on Map<K,V> interface. The BST is a linked binary tree with root reference, both internal and external nodes (MyBSNode) contains (key, value) entries

What do you think? There's something to improve?

public BSPosition<E> insert(int k, E e) {
    if(isEmpty()){
        /* Sets root */
        BSPosition<E> r = new MyBSNode<E>(null);
        r.setElement(k, e);
        setRoot(r);
        size++;
        return r;
    }

    BSPosition<E> n = treeInsert(k, root);          //k-key node or last node visited
    if(k == n.getKey()){                            //tree has already a k-key node
        n.setElement(k, e);                         //only modifies e
        return n;           
    }
    /* n is a external (last visited) node with different key */
    size++;
    if(k < n.getKey())
        return n.setLeftChild(k, e);
    else 
        return n.setRightChild(k, e);

}

private BSPosition<E> treeInsert(int k, BSPosition<E> v){
    if(isLeaf(v))                       return v;           

    if(k < v.getKey()){
        if(v.getLeftChild() == null)    return v;
        return treeInsert(k, v.getLeftChild());
    }
    else if(k == v.getKey())            return v;

    else{
        if(v.getRightChild() == null)   return v;
        return treeInsert(k, v.getRightChild());
    }
}

Answer 1

The algorithm looks fine. Some other notes:

1. I would use longer variable names than r, k, e etc. Longer names would make the code more readable since readers/maintainers don't have to decode or memorize the abbreviations.

2. new MyBSNode<E>(null)
   

   Consider creating a default contructor, a named factory method or an explanatory local variable for null. Currently readers have to check the MyBSNode constructor to figure out what's that null supposed to mean.

3. MyBSNode does not seem to have a good name. Try to find something more descriptive.

4. n.setElement(k, e); // only modifies e
   

   Creating a setValue(E value) method would make the comment unnecessary and would be cleaner.

5. I'd consider moving isLeaf to BSPosition since it seems data envy. I guess its only task is to check that both left and right children are nulls.

6. treeInsert does not do any insertion, its name is a little bit misleading, it just searches the parent of the new node or a node with the same key. I'd call it according to that. (searchInsertionPoint for example.)