Implementation of binary search tree add algorithm

Question

I have to implement an add method for a BST in java, but can not get my add function to work. Could someone help me out?

private boolean add(E x, BinaryNode<E> currentNode){

        if (currentNode == null){
            currentNode = new BinaryNode<>(x);
            size++;
            return true;
        }

        if (currentNode.element.compareTo(x) == 0){
            return false;
        }

        else if((currentNode.element.compareTo(x) < 0)){

            if(currentNode.left == null){
                currentNode.left = new BinaryNode<>(x);
                size++;
                return true;

            } else {
                add(x, currentNode.left);
            }

        }

        else if(currentNode.element.compareTo(x) > 0){

            if(currentNode.right == null){
                currentNode.right = new BinaryNode<>(x);
                size++;
                return true;

            } else {
                add(x, currentNode.right);
            }

        }

        return false;
    }

    public boolean add(E x){
        return this.add(x, root);
    }

Answer 1

One problem I see is that when you assign the root element you assign it to a local variable. This obviously doesn't work.

private boolean add(E x, BinaryNode<E> currentNode){
  /////// REMOVE
        if (currentNode == null){
            currentNode = new BinaryNode<>(x);
            size++;
            return true;
        }
  ///////

And add this

public boolean add(E x){
    if( root == null ) {
      root = new BinaryNode<>(x);
      size++;
      return true;
    }  else
      return this.add(x, root);
}

Answer 2

Basically, the root of subtree might change, and this is a recursion, to make it work the return value should be the new root of the subtree, despite it changed or not.

Following are the add() method taken from my BST impl in Java, that with all test cases passed:

/**
 * Add a new value.
 *
 * @param v
 */
@Override
public void add(T v) {
    root = add(root, v);
}

/**
 * Add to a subtree start from given node.
 *
 * @param current root of a subtree to add node to,
 * @param v
 * @return the new root of subtree,
 */
protected BSTNode<T> add(BSTNode<T> current, T v) {
    if (current == null) { // subtree is empty,
        size++;
        return new BSTNode<>(v);
    }

    // compare,
    int compareFlag = v.compareTo(current.value);

    // check this or subtree,
    if (compareFlag < 0) { // smaller, go to left subtree,
        current.left = add(current.left, v);
    } else if (compareFlag > 0) { // larger, go to right subtree,
        current.right = add(current.right, v);
    } else { // equals, ignore it,
    }

    return current;
}