Why does my java program fail the test case for a single number?

Question

Why does my program return false for containing the number '128' in the main method? All other numbers that I have tested seem to work fine (return true when true, and return false when false) but for some reason, the number 128 return false when it is indeed present. This is causing it to fail a test case in my grading system. Can anybody help me spot the error here?

My code is given below:

public class BSTContains {
 public static void main(String[] args) {
  BinarySearchTree<Integer> iBst = new BinarySearchTree<>();
  iBst.add(128);
  iBst.add(12);
  iBst.add(8);
  iBst.add(2);
  iBst.add(6);
  iBst.add(4);
  
  boolean found = iBst.contains(128);
  // The following statement should print true, but actually prints false
  System.out.println(found);
 }

 static class BinarySearchTree<T extends Comparable<T>> {
  private Node root;
  private int size;
  private class Node {
     T element;
     Node left;
     Node right;
  
     public Node(T elem) {
        element = elem;
        left = null;
        right = null;
     }
  }

  public boolean contains(T value) {
  //make current node root
     Node current = root;
  //search until end of tree
     while (current != null) { 
     //base case , if value = current, return true 
        if (current.element == value) {
           return true;
        }
        //if value is > current element
        else if (root.element.compareTo(value) < 0) {
        //search right side of tree
           current = current.right;
        }
        //if value is < current element
        else {
        //search left side of tree
           current = current.left;
        }
     }
  //value not found
     return false;
  }

  public void add(T element) {
     // special case if empty
     if (root == null) {
        root = new Node(element);
        size++;
        return;
     }
  
     // find where this element should be in the tree
     Node n = root;
     Node parent = null;
     int cmp = 0;
     while (n != null) {
        parent = n;
        cmp = element.compareTo(parent.element);
        if (cmp == 0) {
           // don't add a duplicate
           return;
        } else if (cmp < 0) {
           n = n.left;
        } else {
           n = n.right;
        }
     }
  
     // add element to the appropriate empty subtree of parent
     if (cmp < 0) {
        parent.left = new Node(element);
     } else {
        parent.right = new Node(element);
     }
     size++;
    }
 }
}

should have clarified question better. It should return true that 128 is present, but the program returns false. all other numbers are accurate that i have checked — Noah Jones, Nov 29 '21 at 14:32
The comment in the code says *"The following statement should print false."* but that seems to be the one you're saying should be true (and it would make sense for it to be true). About half of the code in your question isn't necessary to reproduce the issue; I will edit out the unnecessary parts. — kaya3, Nov 29 '21 at 14:35

score 4 · Answer 1 · answered Nov 29 '21 at 14:33

The problem is with

current.element == value

You should use .equals to check if two objects are equal.

Integer caches values in the range -128 to 127 and hence it worked for values lesser than 128.

See:

Why does my java program fail the test case for a single number?

1 Answers1