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) {
  // Uses a recursive (private) helper insert
  root = remove(root, t);
}

/* removes node with given value in the subtree rooted
   at given node and returns modified subtree. */
private Node<T> remove(Node<T> node, T t) {
  if (node == null) { // base case
    return node;
  }
  // find the node that contains "t"
  if (node.data.compareTo(t) > 0) {
    node.left = remove(node.left, t);
  } else if (node.data.compareTo(t) < 0) {
    node.right = remove(node.right, t);
  } else { // found it; let's remove it!
    // zero or one child
    if (node.right == null) {
      return node.left;
    } else if (node.left == null) {
      return node.right;
    }
    // two children
    Node<T> next = findSmallest(node.right);
    node.data = next.data;
    node.right = remove(node.right, next.data);
    numElements--;
  }

  return node;
}

// find the smallest value in subtree rooted at node
// Pre: node != null
private Node<T> findSmallest(Node<T> node) {
  Node<T> small = node;
  while (small.left != null) {
    // go left as far as we can
    small = small.left;
  }
  return small;
}