Java:

Add the following new methods in Binary Search Tree

/** Displays the nodes in a breadth-first traversal */

public void breadthFirstTraversal()

/** Returns the height of this binary tree */

public int height()

Write a main method that tests your implementation of the doubly linked list by doing the following:

Create an empty BinarySearchTree of Strings and add the Strings Red and Green to it, displaying the height of the tree after each element is added.

Create a new BinarySearchTree with the following String elements, in this order:

Tom, George, Jean, Jane, Kevin, Peter, Susan, Jen, Kim, Michael, Michelle

Perform breadthFirstTraversal of the BST and display its height.

Create a new BinarySearchTree with the following Integer elements, in this order:

50, 45, 35, 48, 59, 51, 58

Perform breadthFirstTraversal of the BST and display its height.

Output should look like:

Empty tree of Strings created. The height of the tree is 0

After Red is added the height of the tree is 1

After Green is added the height of the tree is 2

Creating a new BinarySearchTree with the following String elements:

Tom, George, Jean, Jane, Kevin, Peter, Susan, Jen, Kim, Michael, Michelle.

The breadth-first traversal is Tom George Jean Jane Kevin Jen Peter Kim Susan Michael Michelle

The height of the tree is 8

Creating a new BinarySearchTree with the following Integers:

50, 45, 35, 48, 59, 51, 58

The breadth-first traversal for the tree is 50 45 59 35 48 51 58

The height of the tree is 4