I had to make a Balanced Binary Search Tree and I think I have it right but would like your opinion whether I am right or not, please.

Here is the code that I wrote for it:

package util; import java.util.Iterator; import java.util.NoSuchElementException; /*Author: D3158*/ /** * A <code>BinarySearchTree</code>(BST) implements the <code>BinarySearchTreeADT</code> * interface, allowing <code>Comparable</code> objects to be inserted or * removed. At all times, the tree is balanced (i.e. -1 <= balance factor <= 1 * at every node in the tree). * * <p>The <code>BinarySearchTree</code> has two constructors: * <ul> * <li>a default constructor</li> * <li>a constructor that has a <code>Comparable</code> item as a parameter</li> * </ul></p> * <p>The public methods implement the <code>BinarySearchTreeADT</code> interface.</p> * <p>The implementation of this class is the lab 4 assignment for COMP 139 students.</p> */ public class BinarySearchTree implements BinarySearchTreeADT { private static final String INDENT = " "; private Node root; // The root of the BST. /** * Create a blank String that consists of a set of indents. * @param indent the number of indents. * @return a String that contains 'indent' * INDENT.length() spaces. */ private static String makeIndents(int indent) { String result = ""; for (int i = 0; i < indent; i++) { result = result + BinarySearchTree.INDENT; } return result; } @Override public final void add(Comparable item) { this.root = addIterative(item, this.root); } private Node addIterative(Comparable item, Node n) { Node originalTree = n; // If the tree is empty, just create a new tree with one node. if (n == null) { Node newNode = new Node(); newNode.item = item; return newNode; } // Find the insertion point. while (n != null) { int compare = item.compareTo(n.item); // Duplicate items are not allowed. if (compare == 0) throw new DuplicateElementException(); // See if item belongs in the left subtree. if (compare < 0) { // If there is space then add a new node; otherwise, // keep looking for space. if (n.left == null) { n.left = new Node(); n.left.item = item; //break; // Node added, don't look any more return balanceTree(); } else n = n.left; } // The item must belong in the right subtree. else { // If there is space then add a new node; otherwise, // keep looking for space. if (n.right == null) { n.right = new Node(); n.right.item = item; //break; // Node added, don't look any more. return balanceTree(); } else n = n.right; } } return originalTree; } private Node balanceTree(){ // Create a new node then use get getBalanceFactor to get balance rotation // by calling left rotation, right rotation, left right rotation, left right // rotation if (root.getBalanceFactor()!= 2 && root.getBalanceFactor()!= 2) return root; Node newRootHere = new Node(); if (root.getBalanceFactor() == -2 && root.left.getBalanceFactor()== -1) { newRootHere = rightRotation(root, root.left); } if (root.getBalanceFactor()== 2 && root.right.getBalanceFactor()== 1) { newRootHere = leftRotation(root, root.right); } if (root.getBalanceFactor()== 2 && root.right.getBalanceFactor()== -1) { Node tempNode = rightRotation(root.right,root.right.left); newRootHere = leftRotation(root, tempNode); } if (root.getBalanceFactor()== -2 && root.left.getBalanceFactor()== 1) { newRootHere = leftRotation(root, root.left); } if (root.getBalanceFactor()== 2 && root.right.getBalanceFactor()== 0) { newRootHere = leftRotation(root, root.right); } if (root.getBalanceFactor()== -2 && root.left.getBalanceFactor()== 0) { newRootHere = rightRotation(root, root.left); } return newRootHere; } private Node leftRotation(Node oldRoot, Node newRoot){ // Pushes a node down and to the left to balance the tree. // Right child replaces the old one to the new right child's // left child and becomes it's right child Node newroot = newRoot; oldRoot.right = newroot.left; newroot.left = oldRoot; return newroot; } private Node rightRotation(Node oldRoot, Node newRoot){ // Pushes a node down and to the right to balance the tree. // Left child replaces the old one to the new left child's // right child and becomes it's left child Node newroot = newRoot; oldRoot.left = newroot.right; newroot.right = oldRoot; return newroot; } @Override public Iterator<Comparable> iterator() /*throws ConcurrentModificationException, UnsupportedOperationException*/ { return new BinarySearchTreeIterator(); } private final class BinarySearchTreeIterator implements Iterator<Comparable> { private int root; private BinarySearchTreeIterator() { this.root = 0; } @Override public boolean hasNext() { throw new UnsupportedOperationException("Not supported yet."); } @Override public Comparable next() { throw new UnsupportedOperationException("Not supported yet."); } @Override public void remove() { throw new UnsupportedOperationException("Not supported yet."); } } @Override public String printTree() { if (this.root == null) return ""; return "\n" + printTree(this.root, 0); } /** * Create a string representation for a subtree of a binary search tree. * @param root the node at the root of the subtree. * @param level the node level (in the entire tree) for the root of this subtree. * @return a diagram, as a <code>String</code>, that represents this subtree. */ private String printTree(Node root, int level) { String result = ""; if (root.right != null) { result = result + printTree(root.right, level + 1); } result = result + makeIndents(level) + root.item.toString() + "(" + root.getBalanceFactor() + ")\n"; if (root.left != null) { result = result + printTree(root.left, level + 1); } return result; } @Override public void remove(Comparable item) { //this.root = removeIterativeAlmost(item, this.root); this.root = removeIterativeAlmost(item, this.root); } private Node removeIterativeAlmost(Comparable item, Node n) { // Find the node that contains the item to be removed and // the parent of that node. Node parent = null; Node toremove = n; while (toremove != null) { // Check to see if the item has been found. int compare = item.compareTo(toremove.item); if (compare == 0) break; // If not found, look in the appropriate subtree. parent = toremove; if (compare < 0) toremove = toremove.left; else toremove = toremove.right; } // Item was either found (toremove != null) or the item is not in the // tree (toremove == null). if (toremove == null) throw new NoSuchElementException(); // If the node to be removed has no more than one child // then replace it with the other child. if (toremove.left == null) { replaceChildNodeInParent(parent, toremove, toremove.right); return n; } if (toremove.right == null) { replaceChildNodeInParent(parent, toremove, toremove.left); return n; } // The node to remove has two children. // 1. Find a replacemant value. // 2. Replace the value in the node to remove. // 3. Remove the node that contains the replacement value. Comparable largest = findLargest(toremove.left); toremove.item = largest; toremove.left = removeIterativeAlmost(largest, toremove.left); return n; } private void replaceChildNodeInParent( Node parent, Node currentchild, Node newchild) { if (parent == null) this.root = newchild; else if (parent.left == currentchild) parent.left = newchild; else parent.right = newchild; } /** * Find the largest value in the tree with 'n' as its root. * @param n the root of the tree. * @return the rightmost value in the tree. */ private Comparable findLargest(Node n) { while (n.right != null) { n = n.right; } return n.item; } /** * Find the smallest value in the tree with 'n' as its root. * @param n the root of the tree. * @return the leftmost value in the tree. */ private Comparable findSmallest(Node n) { while (n.left != null) { n = n.left; } return n.item; } /** * Define the data structure of a node in a balanced binary search tree. */ private class Node { private Comparable item; // The data item. private Node left; // The root of the left subtree. private Node right; // The root of the right subtree. /** * Determine the balance factor for this node. * @return the difference between the right height and the left height. */ private int getBalanceFactor() { // Note: This code needs to be replaced. It is here so that printTree() // has a working getBalanceFactor() method to use. //return -999; int leftHeight = (left == null)?0:left.height(); int rightHeight = (right == null)?0:right.height(); return rightHeight - leftHeight; } private int height(){ int leftHeight = (left == null)?0:left.height(); int rightHeight = (right == null)?0:right.height(); return 1 + Math.max(leftHeight, rightHeight); } } }

Below is the output diagram

UUOutput.jpg

Also, I am having hard time doing the iterator using ArrayList. I tried to do it with Stack but I don't know where to begin. Algorithm or pseudo code or the code, whatever you like to share with me, is appreciated.

Thank you

ps. I have other files to go with this so let me know if you would like to take a look at it.