""JAVA""

Problem 1: Write a method that prints the tree in pre-order, but without using recursion.

You will need a stack of Nodes to do this. Heres the general idea:

Start WALKER at the ROOT. Then:

Print WALKERs value.

Push WALKERs right child onto the stack.

Move WALKER to the left.

Repeat the above three steps until WALKER becomes null (i.e. it cant go left any further). At that point, pop a Node off the stack. Set WALKER to this Node and repeat the above three steps again. Keep doing this until WALKER is null and the stack is empty. Avoid pushing null onto the stack!

Problem 2: Now that you know how to traverse a tree without using recursion, you can create an iterator for the binary search tree. (Yay! Iterator!) Create the class TreeIterator inside the BST class that implements the Iterator interface.

Implement both the hasNext and next methods. The remove method can just throw the UnsupportedOperationException. The iterator should traverse the tree in pre-order fashion.

public class BST> { // Binary search tree is made out of Node objects private class Node { E element; // Data element stored in this node Node left; // Reference to left child Node right; // Reference to right child } private Node root; // Root of this binary search tree private int size; // Number of elements stored in this tree /** * Prints (to standard output) this tree's elements in order. */ public void printInorder() { printInorder(root); System.out.println(); } // Worker method private void printInorder(Node w) { if (w != null) { printInorder(w.left); System.out.print(w.element+" "); printInorder(w.right); } } /** * Prints (to standard output) this tree's elements in pre-order. */ public void printPreorder() { printPreorder(root); System.out.println(); } // Worker method private void printPreorder(Node w) { if (w != null) { System.out.print(w.element+" "); printPreorder(w.left); printPreorder(w.right); } } /** * Returns true if this tree has no elements. * @return true if tree is empty */ public boolean isEmpty() { return root == null; } /** * Returns the number of elements in this tree. * @return size of tree */ public int size() { return size; } /** * Returns true if specified element is in this tree. * @param x element to find * @return true if element is in this tree */ public boolean contains(E x) { return contains(x, root); } // Worker method private boolean contains(E x, Node w) { if (w == null) return false; else if (x.equals(w.element)) return true; else if (x.compareTo(w.element) < 0) return contains(x, w.left); else return contains(x, w.right); } /** * Adds the specified element to this tree. * @param x element to add */ public void add(E x) { root = add(x, root); size++; } // Worker method private Node add(E x, Node w) { if (w == null) { Node n = new Node(); n.element = x; return n; } else if (x.compareTo(w.element) < 0) { w.left = add(x, w.left); } else { w.right = add(x, w.right); } return w; } }