Using the BinarySearchTree class given below,

Write a method findHeight() that returns the height of the calling tree. Remember that the height is the maximum level of the tree, with level 1 being the root. (Hint: A recursive solution is nice and short.)

Write a levelOrderTraversal method. The method should print the nodes in the order that they are visited. (Hint: one non-recursive algorithm for this is to use a queue to keep track of the nodes that you want to visit. Start by enqueuing the root node, and see what needs to be done from there.)

BinarySearchTree.java

import java.util.Iterator;

import java.util.LinkedList;

import java.util.Queue;

import java.util.Stack;

/*

* This class implements a binary search tree.

*/

// The > means that whatever type we store in the tree

// must be from a class that implements the Comparable interface (i.e., provides

// a definition for the compareTo method).

//

// Any class that provides an iterator() method can implement the Iterable

// interface. This allows us to use the enhanced for syntax with objects of this class.

public class BinarySearchTree> implements Iterable {

// This nested class implements an in-order iterator over the elements of this BST

// (i.e., the elements are returned in the same order as an in-order traversal).

private class InOrderIterator implements Iterator { // Since InOrderIterator is not static, it *does* have access to the instance variables of BST.

private Node current = root;

private Stack> pile = new Stack<>();

@Override

public boolean hasNext() {

return !(current == null && pile.empty());

}

@Override

public E next() {

while (current != null) {

pile.push(current);

current = current.left;

}

Node popped = pile.pop();

current = popped.right;

return popped.data;