There is BinarySearchTree class When removing a node from a

There is BinarySearchTree class. When removing a node from a BST, we can replace it with either its predecessor or its successor. Complete the predecessor() method

so that it returns the node that comes immediately before e. Hint: the work needed to find the predecessor is a mirror image of what is required to find a node\'s

successor, so use successor() as a resource.

BinarySearchTree class:

Solution

import java.util.AbstractSet;
import java.util.Iterator;

public class BinarySearchTree<E extends Comparable<E>> extends AbstractSet<E> {
protected BTNode<E> root;

protected int size;

/**
   * Initializes this BinarySearchTree object to be empty, to contain only
   * elements of type E, to be ordered by the Comparable interface, and to
   * contain no duplicate elements.
   */
public BinarySearchTree() {
    root = null;
    size = 0;
}

/**
   * Initializes this BinarySearchTree object to contain a shallow copy of a
   * specified BinarySearchTree object. The worstTime(n) is O(n), where n is the
   * number of elements in the specified BinarySearchTree object.
   *
   * @param otherTree - the specified BinarySearchTree object that this
   *          BinarySearchTree object will be assigned a shallow copy of.
   */
public BinarySearchTree(BinarySearchTree<? extends E> otherTree) {
    root = copy(otherTree.root, null);
    size = otherTree.size;
}

protected BTNode<E> copy(BTNode<? extends E> p, BTNode<E> parent) {
    if (p != null) {
      BTNode<E> q = new BTNode<E>(p.element, parent);
      q.left = copy(p.left, q);
      q.right = copy(p.right, q);
      return q;
    }
    return null;
} // method copy

/**
   * Finds the predecessor of a specified BTNode object in this BinarySearchTree. The worstTime(n) is O(n) and
   * averageTime(n) is constant.
   *
   * @param e - the BTNode object whose successor is to be found.
   * @return the successor of e, if e has a successor; otherwise, return null.
   */
protected BTNode<E> predecessor(BTNode<E> e) {
    if (e == null) {
      return null;
    } else if (e.left != null) {
      // successor is leftmost BTNode in right subtree of e
      BTNode<E> p = e.left;
      while (p.right != null) {
        p = p.right;
      }
      return p;

    } // e has a right child
    else {

      // go up the tree to the right as far as possible, then go up
      // to the left.
      BTNode<E> p = e.parent;
      BTNode<E> ch = e;
      while ((p != null) && (ch == p.left)) {
        ch = p;
        p = p.parent;
      } // while
      return p;
    } // e has no left child
   // method successor
}

@SuppressWarnings(\"unchecked\")
@Override
public boolean equals(Object obj) {
    if (!(obj instanceof BinarySearchTree)) {
      return false;
    }
    return equals(root, ((BinarySearchTree<? extends E>) obj).root);
} // method 1-parameter equals

public boolean equals(BTNode<E> p, BTNode<? extends E> q) {
    if ((p == null) || (q == null)) {
      return p == q;
    }
    if (!p.element.equals(q.element)) {
      return false;
    }
    if (equals(p.left, q.left) && equals(p.right, q.right)) {
      return true;
    }
    return false;
}

/**
   * Returns the size of this BinarySearchTree object.
   *
   * @return the size of this BinarySearchTree object.
   */
@Override
public int size() {
    return size;
}

/**
   * Iterator method will be implemented for a future
   *
   * @return an iterator positioned at the smallest element in this
   *         BinarySearchTree object.
   */
@Override
public Iterator<E> iterator() {
    // Skipped in preparation for next week
    throw new UnsupportedOperationException(\"Not implemented yet!\");
}

/**
   * Determines if there is at least one element in this BinarySearchTree object
   * that equals a specified element. The worstTime(n) is O(n) and
   * averageTime(n) is O(log n).
   *
   * @param obj - the element sought in this BinarySearchTree object.
   * @return true - if there is an element in this BinarySearchTree object that
   *         equals obj; otherwise, return false.
   * @throws ClassCastException - if obj cannot be compared to the elements in
   *           this BinarySearchTree object.
   * @throws NullPointerException - if obj is null.
   */
@Override
public boolean contains(Object obj) {
    return getBTNode(obj) != null;
}

/**
   * Ensures that this BinarySearchTree object contains a specified element. The
   * worstTime(n) is O(n) and averageTime(n) is O(log n).
   *
   * @param element - the element whose presence is ensured in this
   *          BinarySearchTree object.
   * @return true - if this BinarySearchTree object changed as a result of this
   *         method call (that is, if element was actually inserted); otherwise,
   *         return false.
   * @throws ClassCastException - if element cannot be compared to the elements
   *           already in this BinarySearchTree object.
   * @throws NullPointerException - if element is null.
   */
@Override
public boolean add(E element) {
    if (root == null) {
      if (element == null) {
        throw new NullPointerException();
      }
      root = new BTNode<E>(element, null);
      size++ ;
      return true;
    }
    else {
      BTNode<E> temp = root;

      int comp;

      while (true) {
        comp = element.compareTo(temp.element);
        if (comp == 0) {
          return false;
        }
        if (comp < 0) {
          if (temp.left != null) {
            temp = temp.left;
          } else {
            temp.left = new BTNode<E>(element, temp);
            size++ ;
            return true;
          } // temp.left == null
        } else if (temp.right != null) {
          temp = temp.right;
        } else {
          temp.right = new BTNode<E>(element, temp);
          size++ ;
          return true;
        } // temp.right == null
      } // while
    } // root not null
} // method add

/**
   * Ensures that this BinarySearchTree object does not contain a specified
   * element. The worstTime(n) is O(n) and averageTime(n) is O(log n).
   *
   * @param obj - the object whose absence is ensured in this BinarySearchTree
   *          object.
   * @return true - if this BinarySearchTree object changed as a result of this
   *         method call (that is, if obj was actually removed); otherwise,
   *         return false.
   * @throws ClassCastException - if obj cannot be compared to the elements
   *           already in this BinarySearchTree object.
   * @throws NullPointerException - if obj is null.
   */
@Override
public boolean remove(Object obj) {
    BTNode<E> e = getBTNode(obj);
    if (e == null) {
      return false;
    }
    deleteBTNode(e);
    return true;
}

/**
   * Finds the BTNode object that houses a specified element, if there is such an BTNode. The worstTime(n) is O(n), and
   * averageTime(n) is O(log n).
   *
   * @param obj - the element whose BTNode is sought.
   * @return the BTNode object that houses obj - if there is such an BTNode; otherwise, return null.
   * @throws ClassCastException - if obj is not comparable to the elements already in this BinarySearchTree object.
   * @throws NullPointerException - if obj is null.
   */
@SuppressWarnings(\"unchecked\")
protected BTNode<E> getBTNode(Object obj) {
    int comp;

    if (obj == null) {
      throw new NullPointerException();
    }
    if (!(obj instanceof Comparable)) {
      return null;
    }
    Comparable<E> compObj = (Comparable<E>) obj;
    BTNode<E> e = root;
    while (e != null) {
      comp = compObj.compareTo(e.element);
      if (comp == 0) {
        return e;
      } else if (comp < 0) {
        e = e.left;
      } else {
        e = e.right;
      }
    } // while
    return null;
}

/**
   * Deletes the element in a specified BTNode object from this BinarySearchTree.
   *
   * @param p - the BTNode object whose element is to be deleted from this BinarySearchTree object.
   * @return the BTNode object that was actually deleted from this BinarySearchTree object.
   */
protected BTNode<E> deleteBTNode(BTNode<E> p) {
    size-- ;

    // If p has two children, replace p\'s element with p\'s successor\'s
    // element, then make p reference that successor.
    if ((p.left != null) && (p.right != null)) {
      BTNode<E> s = successor(p);
      p.element = s.element;
      p = s;
    } // p had two children

    // At this point, p has either no children or one child.

    BTNode<E> replacement;

    if (p.left != null) {
      replacement = p.left;
    } else {
      replacement = p.right;
    }

    // If p has at least one child, link replacement to p.parent.
    if (replacement != null) {
      replacement.parent = p.parent;
      if (p.parent == null) {
        root = replacement;
      } else if (p == p.parent.left) {
        p.parent.left = replacement;
      } else {
        p.parent.right = replacement;
      }
    } // p has at least one child
    else if (p.parent == null) {
      root = null;
    } else {
      if (p == p.parent.left) {
        p.parent.left = null;
      } else {
        p.parent.right = null;
      }
    } // p has a parent but no children
    return p;
} // method deleteBTNode

/**
   * Finds the successor of a specified BTNode object in this BinarySearchTree. The worstTime(n) is O(n) and
   * averageTime(n) is constant.
   *
   * @param e - the BTNode object whose successor is to be found.
   * @return the successor of e, if e has a successor; otherwise, return null.
   */
protected BTNode<E> successor(BTNode<E> e) {
    if (e == null) {
      return null;
    } else if (e.right != null) {
      // successor is leftmost BTNode in right subtree of e
      BTNode<E> p = e.right;
      while (p.left != null) {
        p = p.left;
      }
      return p;

    } // e has a right child
    else {

      // go up the tree to the left as far as possible, then go up
      // to the right.
      BTNode<E> p = e.parent;
      BTNode<E> ch = e;
      while ((p != null) && (ch == p.right)) {
        ch = p;
        p = p.parent;
      } // while
      return p;
    } // e has no right child
} // method successor

protected static class BTNode<E> {
    protected E element;

    protected BTNode<E> left = null, right = null, parent;

    /**
     * Initializes this BTNode object. This default constructor is defined for the sake of subclasses of the
     * BinarySearchTree class.
     */
    public BTNode() {}

    /**
     * Initializes this BTNode object from element and parent.
     */
    public BTNode(E element, BTNode<E> parent) {
      this.element = element;
      this.parent = parent;
    } // constructor

} // class BTNode

} // class BinarySearchTree