Implement the code using Java.

Binary Tree Programming problem:

Create and test a Binary Search Tree class that stores names in String format. This class will closely parallel the IntTreeSearch code discussed in class and in Canvas.

These are the classes you are going to create (and their IntTreeSearch equivalents in parentheses):

NameTreeNode (IntTreeNode): Stores data for the node, a String, and the left and right subtree nodes. Add a one - argument and three - argument constructor.

NameTreeSearch (IntTreeSearch): Implement these methods:

public NameTreeSearch() { }

public void add(String aName) { }

private NameTreeNode add(NameTreeNode root, String aName) { // Hint: Think Comparable }

public void print() { // Inorder traversal }

private void print(NameTreeNode root) { }

public void printSideways() { }

private void printSideways(NameTreeNode root, int indent) { }

NameTreeTest (IntTreeTest): Provide a test program that does these things: 1)Declares an array of names 2)Initialize array to these values: {"Beth", "Sue", "Dave", "Pat", "Mike", "Dawn", "Cindi", "Gina"} 3)Iterate the array and add the names to your NameTreeSearchby calling add. 4)Produce this exact output:

Sue Pat Mike |Gina Dawn Dave Cindi Beth Beth Cindi Dave Dawn Gina Mike Pat Sue

The first uses the printSideways method and the second uses the print() method that uses Inorder traversal (and proves the binary tree is sorted).