Remove (Implementation)

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

Exercise Complete the implementation of remove.

@Override
public void remove(T t) {
  // TODO Implement Me!
}

Hint: Go for a recursive implementation. An iterative one without having a parent pointer in the Node class will be tough to carry out.

Solution 
@Override
public void remove(T t) {
  root = remove(root, t);
}

// always call as follows: subtree = remove(subtree, data);
private Node<T> remove(Node<T> node, T t) {
  // if node == null, element isn't present --> don't do anything
  if (node != null) {
    int comparisonResult = t.compareTo(node.data);
    if (comparisonResult < 0) {
      node.left = remove(node.left, t);
    } else if (comparisonResult > 0) {
      node.right = remove(node.right, t);
    } else { // comparisonResult == 0 --> found the element!
      node = removeSubtreeRoot(node);
    }
  }
  return node;
}

// always call as follows: subtree = removeSubtreeRoot(subtree)
// pre: node != null
private Node<T> removeSubtreeRoot(Node<T> node) {
  if (node.left == null) {
    node = node.right;
    numElements--;
  } else if (node.right == null) {
    node = node.left;
    numElements--;
  } else { // two children:
    T smallestRight = getSmallestElement(node.right);
    node.data = smallestRight;
    node.right = remove(node.right, smallestRight); // takes care of numElements--
  }
  return node;
}

// pre: node != null
private T getSmallestElement(Node<T> node) {
  while (node.left != null) {
    node = node.left;
  }
  return node.data;
}