BST Operation: Find

  • Implement the core operations of an OrderedSet efficiently with a Binary Search Tree.

The has operation in a BST implementation of OrderedSet ADT can perform a 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 the 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 but more polished recursive implementation!

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);
}