1  public class BST<E> implements Tree<E> {
  2    protected TreeNode<E> root;
  3    protected int size = 0;
  4    protected java.util.Comparator<E> c; 
  5  
  6    /** Create a default BST with a natural order comparator */
  7    public BST() {
  8      this.c = (e1, e2) -> ((Comparable<E>)e1).compareTo(e2);
  9    }
 10  
 11    /** Create a BST with a specified comparator */
 12    public BST(java.util.Comparator<E> c) {
 13      this.c = c;
 14    }
 15  
 16    /** Create a binary tree from an array of objects */
 17    public BST(E[] objects) {
 18      this.c = (e1, e2) -> ((Comparable<E>)e1).compareTo(e2);
 19      for (int i = 0; i < objects.length; i++)
 20        add(objects[i]);
 21    }
 22  
 23    @Override /** Returns true if the element is in the tree */
 24    public boolean search(E e) {
 25      TreeNode<E> current = root; // Start from the root
 26  
 27      while (current != null) {
 28        if (c.compare(e, current.element) < 0) {
 29          current = current.left;
 30        }
 31        else if (c.compare(e, current.element) > 0) {
 32          current = current.right;
 33        }
 34        else // element matches current.element
 35          return true; // Element is found
 36      }
 37  
 38      return false;
 39    }
 40  
 41    @Override /** Insert element e into the binary tree
 42     * Return true if the element is inserted successfully */
 43    public boolean insert(E e) {
 44      if (root == null)
 45        root = createNewNode(e); // Create a new root
 46      else {
 47        // Locate the parent node
 48        TreeNode<E> parent = null;
 49        TreeNode<E> current = root;
 50        while (current != null)
 51          if (c.compare(e, current.element) < 0) {
 52            parent = current;
 53            current = current.left;
 54          }
 55          else if (c.compare(e, current.element) > 0) {
 56            parent = current;
 57            current = current.right;
 58          }
 59          else
 60            return false; // Duplicate node not inserted
 61  
 62        // Create the new node and attach it to the parent node
 63        if (c.compare(e, parent.element) < 0)
 64          parent.left = createNewNode(e);
 65        else
 66          parent.right = createNewNode(e);
 67      }
 68  
 69      size++;
 70      return true; // Element inserted successfully
 71    }
 72  
 73    protected TreeNode<E> createNewNode(E e) {
 74      return new TreeNode<>(e);
 75    }
 76  
 77    @Override /** Inorder traversal from the root */
 78    public void inorder() {
 79      inorder(root);
 80    }
 81  
 82    /** Inorder traversal from a subtree */
 83    protected void inorder(TreeNode<E> root) {
 84      if (root == null) return;
 85      inorder(root.left);
 86      System.out.print(root.element + " ");
 87      inorder(root.right);
 88    }
 89  
 90    @Override /** Postorder traversal from the root */
 91    public void postorder() {
 92      postorder(root);
 93    }
 94  
 95    /** Postorder traversal from a subtree */
 96    protected void postorder(TreeNode<E> root) {
 97      if (root == null) return;
 98      postorder(root.left);
 99      postorder(root.right);
100      System.out.print(root.element + " ");
101    }
102  
103    @Override /** Preorder traversal from the root */
104    public void preorder() {
105      preorder(root);
106    }
107  
108    /** Preorder traversal from a subtree */
109    protected void preorder(TreeNode<E> root) {
110      if (root == null) return;
111      System.out.print(root.element + " ");
112      preorder(root.left);
113      preorder(root.right);
114    }
115  
116    /** This inner class is static, because it does not access 
117        any instance members defined in its outer class */
118    public static class TreeNode<E> {
119      protected E element;
120      protected TreeNode<E> left;
121      protected TreeNode<E> right;
122  
123      public TreeNode(E e) {
124        element = e;
125      }
126    }
127  
128    @Override /** Get the number of nodes in the tree */
129    public int getSize() {
130      return size;
131    }
132  
133    /** Returns the root of the tree */
134    public TreeNode<E> getRoot() {
135      return root;
136    }
137  
138    /** Returns a path from the root leading to the specified element */
139    public java.util.ArrayList<TreeNode<E>> path(E e) {
140      java.util.ArrayList<TreeNode<E>> list =
141        new java.util.ArrayList<>();
142      TreeNode<E> current = root; // Start from the root
143  
144      while (current != null) {
145        list.add(current); // Add the node to the list
146        if (c.compare(e, current.element) < 0) {
147          current = current.left;
148        }
149        else if (c.compare(e, current.element) > 0) {
150          current = current.right;
151        }
152        else
153          break;
154      }
155  
156      return list; // Return an array list of nodes
157    }
158  
159    @Override /** Delete an element from the binary tree.
160     * Return true if the element is deleted successfully
161     * Return false if the element is not in the tree */
162    public boolean delete(E e) {
163      // Locate the node to be deleted and also locate its parent node
164      TreeNode<E> parent = null;
165      TreeNode<E> current = root;
166      while (current != null) {
167        if (c.compare(e, current.element) < 0) {
168          parent = current;
169          current = current.left;
170        }
171        else if (c.compare(e, current.element) > 0) {
172          parent = current;
173          current = current.right;
174        }
175        else
176          break; // Element is in the tree pointed at by current
177      }
178  
179      if (current == null)
180        return false; // Element is not in the tree
181  
182      // Case 1: current has no left child
183      if (current.left == null) {
184        // Connect the parent with the right child of the current node
185        if (parent == null) {
186          root = current.right;
187        }
188        else {
189          if (c.compare(e, parent.element) < 0)
190            parent.left = current.right;
191          else
192            parent.right = current.right;
193        }
194      }
195      else {
196        // Case 2: The current node has a left child
197        // Locate the rightmost node in the left subtree of
198        // the current node and also its parent
199        TreeNode<E> parentOfRightMost = current;
200        TreeNode<E> rightMost = current.left;
201  
202        while (rightMost.right != null) {
203          parentOfRightMost = rightMost;
204          rightMost = rightMost.right; // Keep going to the right
205        }
206  
207        // Replace the element in current by the element in rightMost
208        current.element = rightMost.element;
209  
210        // Eliminate rightmost node
211        if (parentOfRightMost.right == rightMost)
212          parentOfRightMost.right = rightMost.left;
213        else
214          // Special case: parentOfRightMost == current
215          parentOfRightMost.left = rightMost.left;     
216      }
217  
218      size--; // Reduce the size of the tree
219      return true; // Element deleted successfully
220    }
221  
222    @Override /** Obtain an iterator. Use inorder. */
223    public java.util.Iterator<E> iterator() {
224      return new InorderIterator();
225    }
226  
227    // Inner class InorderIterator
228    private class InorderIterator implements java.util.Iterator<E> {
229      // Store the elements in a list
230      private java.util.ArrayList<E> list =
231        new java.util.ArrayList<>();
232      private int current = 0; // Point to the current element in list
233  
234      public InorderIterator() {
235        inorder(); // Traverse binary tree and store elements in list
236      }
237  
238      /** Inorder traversal from the root*/
239      private void inorder() {
240        inorder(root);
241      }
242  
243      /** Inorder traversal from a subtree */
244      private void inorder(TreeNode<E> root) {
245        if (root == null) return;
246        inorder(root.left);
247        list.add(root.element);
248        inorder(root.right);
249      }
250  
251      @Override /** More elements for traversing? */
252      public boolean hasNext() {
253        if (current < list.size())
254          return true;
255  
256        return false;
257      }
258  
259      @Override /** Get the current element and move to the next */
260      public E next() {
261        return list.get(current++);
262      }
263  
264      @Override // Remove the element returned by the last next()
265      public void remove() {
266        if (current == 0) // next() has not been called yet
267          throw new IllegalStateException(); 
268  
269        delete(list.get(--current)); 
270        list.clear(); // Clear the list
271        inorder(); // Rebuild the list
272      }
273    }
274  
275    @Override /** Remove all elements from the tree */
276    public void clear() {
277      root = null;
278      size = 0;
279    }
280  }