Generic binary search tree in Java

Question

I've posted the code before, but this time I believe I fixed the bug with remove.

The class implements a Binary Search Tree without rebalancing, since unbalanced tree is not an issue in my case. I implemented the basic functions to make it minimally functional:

• Add
• Remove
• Contains
• Remove any
• To string
• Size

Code:

package custom.trees;
public class BinarySearchTree<E extends Comparable> {
 private BinaryTree<E> root;
 private int size;
 public void add(E value) {
 if (root == null) {
 root = new BinaryTree<>(value);
 ++size;
 return;
 }
 recursiveAdd(root, value);
 }
 private void recursiveAdd(BinaryTree<E> current, E value) {
 int comparisonResult = current.getValue().compareTo(value);
 if (comparisonResult < 0) {
 if (current.getRightChild() == null) {
 current.setRightChild(new BinaryTree<>(value));
 ++size;
 return;
 }
 recursiveAdd(current.getRightChild(), value);
 } else if (comparisonResult > 0) {
 if (current.getLeftChild() == null) {
 current.setLeftChild(new BinaryTree<>(value));
 ++size;
 }
 recursiveAdd(current.getLeftChild(), value);
 }
 }
 public boolean contains(E value) {
 return containsRecursive(root, value);
 }
 private boolean containsRecursive(BinaryTree<E> current, E value) {
 if (current == null) {
 return false;
 }
 int comparisonResult = value.compareTo(current.getValue());
 if (comparisonResult == 0) {
 return true;
 } else if (comparisonResult < 0) {
 return containsRecursive(current.getLeftChild(), value);
 } else {
 return containsRecursive(current.getRightChild(), value);
 }
 }
 public boolean remove(E value) {
 return removeRecursive(root, null, value);
 }
 private boolean removeRecursive(BinaryTree<E> current, BinaryTree<E> parent, E value) {
 if (current == null) {
 return false;
 }
 int comparisonResult = value.compareTo(current.getValue());
 if (comparisonResult < 0) {
 return removeRecursive(current.getLeftChild(), current, value);
 } else if (comparisonResult > 0) {
 return removeRecursive(current.getRightChild(), current, value);
 }
 int childCount = 0;
 childCount += (current.getLeftChild() == null) ? 0 : 1;
 childCount += (current.getRightChild() == null) ? 0 : 1;
 if (childCount == 0) {
 if (current == root) {
 root = null;
 --size;
 return true;
 }
 if (parent.getLeftChild() == current) {
 parent.setLeftChild(null);
 } else {
 parent.setRightChild(null);
 }
 --size;
 return true;
 } else if (childCount == 1) {
 if (current == root)
 {
 if (root.getLeftChild() != null)
 {
 root = root.getLeftChild();
 }
 else
 {
 root = root.getRightChild();
 }
 --size;
 return true;
 }
 BinaryTree<E> child = (current.getLeftChild() != null) ?
 current.getLeftChild() :
 current.getRightChild();
 if (parent.getLeftChild() == current) {
 parent.setLeftChild(child);
 } else {
 parent.setRightChild(child);
 }
 --size;
 return true;
 }
 //every other case already returned until now
 BinaryTree<E> successor = getLeftMostChild(current.getRightChild());
 current.setValue(successor.getValue());
 BinaryTree<E> successorsParent = current.getRightChild();
 while (successorsParent.getLeftChild() != null && successorsParent.getLeftChild() != successor) {
 successorsParent = successorsParent.getLeftChild();
 }
 if (successorsParent == successor) {
 current.setRightChild(successor.getRightChild());
 } else {
 successorsParent.setLeftChild(successor.getRightChild());
 }
 --size;
 return true;
 }
 public void removeAny()
 {
 if (size == 0)
 {
 throw new IllegalStateException("Calling removeAny on empty tree");
 }
 remove(getLeftMostChild(root).getValue());
 }
 private BinaryTree<E> getLeftMostChild(BinaryTree<E> current)
 {
 while (current.getLeftChild() != null)
 {
 current = current.getLeftChild();
 }
 return current;
 }
 public int size()
 {
 return size;
 }
 @Override
 public String toString()
 {
 StringBuilder builder = new StringBuilder();
 builder.append('[');
 buildString(root, builder);
 if (size != 0)
 {
 builder.deleteCharAt(builder.length() - 1);
 }
 builder.append(']');
 return builder.toString();
 }
 private void buildString(BinaryTree<E> node, StringBuilder builder)
 {
 if (node == null)
 {
 return;
 }
 buildString(node.getLeftChild(), builder);
 builder.append(node.getValue().toString());
 builder.append(' ');
 buildString(node.getRightChild(), builder);
 }
}

I've run tests that are given by my professor and they passed. Also, I run randomized tests with Integer as type parameter. It randomly generated arrays and added/removed from the tree and from the TreeSet from standard library itself. The following code didn't throw after being run 10'000 times:

 BinarySearchTree<Integer> tree = new BinarySearchTree<>();
 Set<Integer> correctAnswer = new TreeSet<>();
 int[] arr = generateRandomizedArray();
 for (int i = 0; i < arr.length; ++i)
 {
 tree.add(arr[i]);
 correctAnswer.add(arr[i]);
 }
 int removeCount = random.nextInt(5, arr.length - 1);
 for (int i = 0; i < removeCount; ++i)
 {
 int val = random.nextInt(0, 30);
 tree.remove(val);
 correctAnswer.remove(val);
 }
 int addCount = random.nextInt(5, VALUE_UPPER_BOUND);
 for (int i = 0; i < addCount; ++i)
 {
 int val = random.nextInt(0, VALUE_UPPER_BOUND);
 tree.add(val);
 correctAnswer.add(val);
 }
 removeCount = random.nextInt(0, tree.size() - 1);
 for (int i = 0; i < removeCount; ++i)
 {
 int val = random.nextInt(0, 40);
 tree.remove(val);
 correctAnswer.remove(val);
 }
 String str = tree.toString();
 String correctStr = correctAnswer.toString();
 StringBuilder builder = new StringBuilder();
 for (int i = 0; i < correctStr.length(); ++i)
 {
 if (correctStr.charAt(i) != ',')
 {
 builder.append(correctStr.charAt(i));
 }
 }
 correctStr = builder.toString();
 if (!str.equals(correctStr))
 {
 throw new TestFailed("answer and correct answer don't match");
 }

The only thing I'm worried about is if internal representation is messed up, but it produces the same output as TreeSet, so I'm calm. As a side effect, the code also tests add() and toString() functions. removeAny() is implemented in terms of remove(), so should be correct as well.

The part of the code that worries me the most is handling cases with root being null, but any other advices on making code better are welcome.

Answer 1

This declaration needs improvement:

public class BinarySearchTree<E extends Comparable> {

With this declaration, the compiler should give you warnings about type safety on these lines:

int comparisonResult = current.getValue().compareTo(value);
// ...
int comparisonResult = value.compareTo(current.getValue());

To fix that, declare like this:

public class BinarySearchTree<E extends Comparable<E>> {

• Incomputable: It did give me a warning (something about raw types)! Currently IntelliJ suggestions is my only source of learning good Java coding style.
• janos: @Incomputable you could try SonarLint for IntelliJ to get more suggestions about code smells and possible bugs. (Disclaimer: I work for the company that makes this tool)