Having trouble using NoSuchElementException in the remove method of an AVL tree

Question

I'm trying to create a remove method that removes a node from an AVL tree. But the program that tests my code is giving me an error saying that I haven't used NoSuchElementException correctly.

Here's the code for my remove method (and the removeRecursive method).

    public T remove(T data) {
        // Base case: if data is null, throw an exception
      if (data == null) {
         throw new IllegalArgumentException("Error: data cannot be null.");
      }
   
        // Recursive helper method for removing data from the tree
      AVLNode<T> removedNode = removeRecursive(root, data);
   
        // If the node is not found, throw NoSuchElementException
      if (removedNode == null) {
         throw new NoSuchElementException("Error: data not found in the tree.");
      }
   
        // Update the root after removal
      root = removedNode;
   
      return removedNode.getData();
   }
   
   private AVLNode<T> removeRecursive(AVLNode<T> current, T data) {
      if (current == null) {
         return null; // Data not found
      }
   
      // Compare data with the current node's data
      int compareResult = data.compareTo(current.getData());
   
      if (compareResult < 0) {
        // Data is smaller, go to the left subtree
         current.setLeft(removeRecursive(current.getLeft(), data));
      } else if (compareResult > 0) {
        // Data is larger, go to the right subtree
         current.setRight(removeRecursive(current.getRight(), data));
      } else {
        // Node with data found, perform removal based on cases
      
         if (current.getLeft() == null && current.getRight() == null) {
            // Case 1: Node is a leaf (no children)
            size--;
            return null;
         } else if (current.getLeft() != null && current.getRight() != null) {
            // Case 3: Node has two children
            // Replace the data with the successor's data
            AVLNode<T> successor = findSuccessor(current.getRight());
            current.setData(successor.getData());
            // Remove the successor node
            current.setRight(removeRecursive(current.getRight(), successor.getData()));
         } else {
            // Case 2: Node has one child
            size--;
            return (current.getLeft() != null) ? current.getLeft() : current.getRight();
         }
      }
   
      // Update height and balance factor, then balance the tree
      return balance(current);
   }

And this is the error it gives me:

[Test Failure: remove] : NoSuchElementException not thrown when attempting to remove data not in the tree.

I'm confused because I am throwing a NoSuchElementException when checking if removedNode is null. So why is it saying that it's not being thrown? Thanks.

Not sure what else to try. Also, I've already tried debugging the program and it still says the same thing.

Answer 1

The problem is that when removeRecursive doesn't find the data, it just returns null at the deepest recursion level. The caller that is one level up in the recursion tree (also removeRecursive), just assigns that null to either the current node's left or right child and returns balance(current) (which will be current itself).

So the null value will not "bubble up" back to the original caller (remove). Instead that caller that got the null return, will just return what balance(current) returns, and its caller will do the same, ... all the way up the recursion tree, until it eventually returns the root node (there's no change in the balance factor).

So remove doesn't get null as return value when the data was not found.

There is also another problem that can occur, which is the inverse: if the tree has just one node, and it is that node that gets deleted, then null will be returned, and NoSuchElementException will be thrown when it actually shouldn't be.

The pragmatic solution is to remove that null check from remove, and instead throw NoSuchElementException in the base case of removeRecursive, instead of returning null there.