Implement the class shown below. The class implements a binary tree. You must write your own test driver. Your class implementation must not depend on the test driver.

public class BinaryTree { //Implements a Binary Tree of Strings private class Node { private Node left; private String data; private Node right; private Node parent; //reference to the parent node } } left = L; data = d; parent = p; // the parent is null for the root node private Node(Node L, String d, Node r, Node p) { right = r; private Node root;

public BinaryTree() { //create an empty tree } public BinaryTree(String d) { //create a tree with a single node } public BinaryTree(BinaryTree b1, String d, BinaryTree b2) { //merge the trees b1 AND b2 with a common root with data d }

public BinaryTree(String t, String open, String close, String empty) { /*create a binary tree from the in order format. Assume t is a syntactically correct string representation of the tree. Open and close are the strings which represent the beginning and end markers of a tree. Empty represents an empty tree. For example, ( ) and ! for open, close and empty respectively. The data in the tree will not include strings matching open, close or empty. All tokens (data, open, close and empty) will be separated by white space. Most of the work should be done in a private recursive method

*/

}

public String toString() { //returns the string representation of the tree using the in order format // discussed in class. If the tree was created from a string use the //the values of open, close and empty given to the constructor otherwise //use (, ) and ! for open, close and empty respectively //most of the work should be done in a recursive private method. } }