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