BST Operation: Find

The has operation in a BST implementation of OrderedSet ADT can perform binary search.

Exercise Complete the implementation of has.

@Override
public boolean has(T t) {
  // TODO Implement me!
  return false;
}

Suggestion: Make use of a private helper find method.

Solution

Here is the implementation of has:

@Override
public boolean has(T t) {
  Node<T> target = find(t);
  return target != null;
}

And this is the implementation of find helper method:

private Node<T> find(T data) {
  Node<T> curr = root;
  while (curr != null) {
    if (curr.data.compareTo(data) > 0) {
      curr = curr.left;
    } else if (curr.data.compareTo(data) < 0) {
      curr = curr.right;
    } else {
      return curr;
    }
  }
  return curr;
}

We could also implement find recursively:

private Node<T> find(Node<T> root, T data) {
  if (root == null) {
    return null;
  }
  if (root.data.compareTo(data) > 0) {
    return find(root.left, data);
  } else if (root.data.compareTo(data) < 0) {
    return find(root.right, data);
  } else {
    return root;
  }
}

Here is the same recursive implementation but slightly polished!

private Node<T> find(Node<T> root, T data) {
  if (root == null || root.data.equals(data)) {
    return root;
  }
  
  if (root.data.compareTo(data) > 0) {
    return find(root.left, data);
  }
  
  return find(root.right, data);
}