Question about adding a node to a binary search tree

Question

I'm coding a binary search tree with all its methods and I've run across the add method, but there's one line that's messing with me.

Here's what I have for the method so far:

// 6) Methods: add

public boolean add(int newData) {
    if (!treeContains(newData)) return false;
    
    else {
        add(root, newData);
        nodeCount++;
        return true;    
    }
}

public Node add(Node node, int newData) {
    
    if (node == null) {
        node = new Node(newData, null, null);               // QUESTION
    }
    
    if (newData > node.data) {
        add(node.rightChild, newData);
        }
    else {                                                  // else if newData is less or equal to node data
        add(node.leftChild, newData);
        }
    return node;
}

Over where I wrote "// QUESTION ", I understand that if we get there, we're basically already standing in the node.leftChild or node.rightChild of some node, so when we create a node (in // QUESTION) it just automatically pops up there? It's just a bit confusing because it feels like I should be specifying that the new node goes there like using something like:

node.leftChild == node;  // (or node.rightChild)

If anyone has a good perspective on this I would really appreciate it. Thanks!

Answer 1

The node that your are passing to add method IMHO should never be null. You should handle the null case before this method is called.

I guess that you need something like that:

public Node add(Node node, int newData) {
  if (newData == node.data) {
    // ??? Not sure what do you need here, but it's there already.
    return node;
  }
  if (newData > node.data) {
    if (node.rightChild == null) {
      node.rightChild = new Node(newData, null, null);
      return node.rightChild;
    } else {
      return add(node.rightChild, newData);
    }
  } else {                                                  
    if (node.leftChild == null) {
      node.leftChild = new Node(newData, null, null);
      return node.leftChild;
    } else {
      return add(node.leftChild, newData);
    }
  }
}

Btw. not sure if this line is correct:

 if (!treeContains(newData)) return false;

Shouldn't the add() method return false if the node is already present? And add it if it's not present? Are you sure that you need a negation in IF?