Binary Search tree won't add new nodes?

Question

I am trying to write a recursive method to add a node to a binary search tree (that does not allow duplicates). For some reason, the method only works when the tree is empty, otherwise it prints out "Duplicate" (even if it is not a duplicate). I am new to programming and would appreciate help and tips to fix this. Thank you.

//add new node to the tree
public void add(int data) {
    Node<Integer> newNode = new Node<>(data); //create new node with the data

    //if the tree is empty, the newNode becomes the root
    if (size() == 0) {
        root = newNode;
        return;
    }
    //otherwise, check if node should be placed to right or left 
    add(data, root);
}
private void add(int data, Node<Integer> node) {
    //base case - found an empty position
    if (node == null) {
        node = new Node<Integer>(data);
    }
    if (data < node.data) {
        add(data, node.left);
    }
    else if (data > node.data) {
        add(data, node.right);
    }
    else if (data == node.data) {
        System.out.println("Duplicate. This value cannot be added to the tree.");
    }
}

Answer 1

When your tree is empty, the node is added properly to it. The first add(int data) function is fine.

The problem exists with the second add(int data, Node<Integer> node) function. In case if the tree already has an element, this method is called. If the node passed is either greater or lesser than the value passed then the function is called again with either the left or right child of the current node. This value might be (will eventually be) null. That leads to creation of a node in the base case of your method which leads to the satisfaction of this data == node.data condition as the node was indeed created with the data value. Hence you get the error message.

In order to fix this, the second function can be altered as below :

private void add(int data, Node<Integer> node) {
    if (data < node.data) {
        if (node.left != null) {
            add(data, node.left);
        } else {
            node.left = new Node<>(data);
        }
    }
    else if (data > node.data) {
        if (node.right != null) {
            add(data, node.right);
        } else {
            node.right = new Node<>(data);
        }
        add(data, node.right);
    }
    else if (data == node.data) {
        System.out.println("Duplicate. This value cannot be added to the tree.");
    }
}

See that the base case has been removed. If ever encountered the base case does not provide us with a reference to any tree node. Hence addition of data to the tree is impossible (the node argument must never be null).

Also, the code adds data as a child to node if the child is null. This guarantees that the method is not recursively with a null node argument and adds data to its rightful place more importantly.