In the BinarySearchTree class, modify the remove method so that a node with two children is replaced by the largest child of the left subtree.

Complete the following file:

BinarySearchTree.java

/** This class implements a binary search tree whose nodes hold objects that implement the Comparable interface. */ public class BinarySearchTree { private Node root; /** Constructs an empty tree. */ public BinarySearchTree() { root = null; } /** Inserts a new node into the tree. @param obj the object to insert */ public void add(Comparable obj) { Node newNode = new Node(); newNode.data = obj; newNode.left = null; newNode.right = null; if (root == null) root = newNode; else root.addNode(newNode); } /** Tries to find an object in the tree. @param obj the object to find @return true if the object is contained in the tree */ public boolean find(Comparable obj) { Node current = root; while (current != null) { int d = current.data.compareTo(obj); if (d == 0) return true; else if (d > 0) current = current.left; else current = current.right; } return false; } /** Tries to remove an object from the tree. Does nothing if the object is not contained in the tree. @param obj the object to remove */ public void remove(Comparable obj) { . . . } /** Prints the contents of the tree in sorted order, showing the subtree structure. */ public void print() { if (root != null) root.printNodes(); System.out.println(); } /** A node of a tree stores a data item and references of the child nodes to the left and to the right. */ private class Node { public Comparable data; public Node left; public Node right; /** Inserts a new node as a descendant of this node. @param newNode the node to insert */ public void addNode(Node newNode) { int comp = newNode.data.compareTo(data); if (comp < 0) { if (left == null) left = newNode; else left.addNode(newNode); } else if (comp > 0) { if (right == null) right = newNode; else right.addNode(newNode); } } /** Prints this node and all of its descendants in sorted order, showing the subtree structure. */ public void printNodes() { if (left != null) { System.out.print("( "); left.printNodes(); System.out.print(") "); } else System.out.print(". "); System.out.print(data + " "); if (right != null) { System.out.print("( "); right.printNodes(); System.out.print(") "); } else System.out.print(". "); } } }

Use the following file:

RemoveTester.java

/**
   A test program for the BinarySearchTree class.
*/
public class RemoveTester
{  
   public static void main(String[] args)
   {  
      BinarySearchTree t = new BinarySearchTree();
      t.add("R");
      t.add("J");
      t.add("T");
      t.add("D");
      t.add("H");
      t.add("S");
      t.add("W");
      
      t.print();
      System.out.println("Expected: ( ( . D ( . H . ) ) J . ) R ( ( . S . ) T ( . W . ) )");
      t.remove("R");
      t.print();
      System.out.println("Expected: ( . D ( . H . ) ) J ( ( . S . ) T ( . W . ) )");
   }
}