Exercise 8 (Binary Search Trees)

Delete a Node from a Binary Search Tree

• Implement an algorithm to delete a node from the binary search tree which we discussed during the lecture.
• Download the source code from the Moodle page and implement the method delete.
  
• Use the method getSuccessor to find the successor if the node to be deleted has two child nodes (like discussed during the lecture).
  

  public class Tree<E extends Comparable<E>> {
      ...
      /**
       * Returns true in case of success and false if the given node was not found.
       */
      public boolean delete(E node) {
          // TODO: Implement this algorithm.
      }
      private Node<E> getSuccessor(Node<E> delNode) {
      ...
  }
  

• Write a short documentation how the delete node algorithm works (format txt or pdf). Explain why the algorithm works (also the sub-algorithm to find a successor).
  

Hints

Take care of the case where the node to be deleted is the root. There are three cases for the node to be deleted:

1. The node is a leaf.
2. The node has one child node.
3. The node has two child nodes.