public class MyTrie {

private TreeNode root = null;

private int numNodes;

// Constructor. Note that an empty trie (no strings added) contains the root node

public MyTrie() {

root = new TreeNode(null, null, null,false);

numNodes=1;

}

// Method to be implemented by you. See handout part 1A

public boolean insert(String s) {

// ***** method code to be added in this class *****

// now we just have a dummy that prints message and returns true.

System.out.println("insert(String) not implemented!");

return true;

}

// Method to be implemented by you. See handout part 1A

public boolean search(String s) {

// **** method code to be added in this class *****

// now we just have a dummy that prints message and returns true.

System.out.println("search(String) not implemented!");

return true;

}

// Method to be implemented by you. See handout part 1A

public void printStringsInLexicoOrder() {

// ***** method code to be added in this class *****

// now we just have a dummy method that prints a message.

System.out.println("printStringsInLexicoOrder() not implemented!");

}

// the following method that calls its recursive counterpart

// prints the tree and its boolean values at nodes in

// in-order traversal order

public void printInOrder() { // not to be changed

printInOrder(root);

}

private void printInOrder(TreeNode N) { // not to be changed

System.out.print("(");

if (N!=null) {

printInOrder(N.getLeftChild());

System.out.print(N.getIsUsed());

printInOrder(N.getRightChild());

}

System.out.print(")");

}

public TreeNode root() { // not to be changed

return root;

}

public int numNodes() { // not to be changed

return numNodes;

}

}

public class MyTrie {

private TreeNode root = null;

private int numNodes;

// Constructor. Note that an empty trie (no strings added) contains the root node

public MyTrie() {

root = new TreeNode(null, null, null,false);

numNodes=1;

}

// Method to be implemented by you. See handout part 1A

public boolean insert(String s) {

// ***** method code to be added in this class *****

// now we just have a dummy that prints message and returns true.

System.out.println("insert(String) not implemented!");

return true;

}

// Method to be implemented by you. See handout part 1A

public boolean search(String s) {

// **** method code to be added in this class *****

// now we just have a dummy that prints message and returns true.

System.out.println("search(String) not implemented!");

return true;

}

// Method to be implemented by you. See handout part 1A

public void printStringsInLexicoOrder() {

// ***** method code to be added in this class *****

// now we just have a dummy method that prints a message.

System.out.println("printStringsInLexicoOrder() not implemented!");

}

// the following method that calls its recursive counterpart

// prints the tree and its boolean values at nodes in

// in-order traversal order

public void printInOrder() { // not to be changed

printInOrder(root);

}

private void printInOrder(TreeNode N) { // not to be changed

System.out.print("(");

if (N!=null) {

printInOrder(N.getLeftChild());

System.out.print(N.getIsUsed());

printInOrder(N.getRightChild());

}

System.out.print(")");

}

public TreeNode root() { // not to be changed

return root;

}

public int numNodes() { // not to be changed

return numNodes;

}

}

Question 1) Using tries for sorting a list of binary strings in lexicographical order. You are given a startup code with classes TreeNode, MyTrie, TestTry. TreeNode is a node in the trie, MyTrie stores the trie as in Figure 2 and TestTry is a sample code that does some tests for class MyTrie. TreeNode and TestTry must not be changed, while you can change class MyTrie. You are allowed to add extra methods or member variables, and add code to given methods, but the signature of the given methods should not be changed. Most methods of MyTrie are not implemented and implementing them is part of your task. Part 1A) (55 marks 25+15+15) Implement the missing code in the following methods of class myTrie public boolean insert (String s): This method "inserts" a string in the trie by adding appropriate nodes to the tree to represent the string. Note that the node representing the given string must have the flag "isUsed" set to true, while intermediate nodes that do not represent any of the strings inserted into the tree will have flag "isUsed" equal to false. If the string being inserted is already present in the trie, return false, otherwise insert the string and return true. public boolean search(String s): Returns true if and only if the string is "stored" in the trie. public void printStringsInLexicoOrderO This method will print, in lexicographical order, all strings that are "stored" in the trie. This printing can be done by an appropriate tree traversal. Note that it may be useful to do some of this traversal recursively, and you are free to add another private auxiliary recursive method that will do most of this traversal/printing Important: This method should be efficient and run in Theta(N) where N is the sum of the lengths of all the binary strings stored in the trie While you are testing and implementing, you may find useful to check that your tree is being built in the right way. For this purpose we provide the method printlnOrder0 that prints the tree using an inorder traversal that prints for each node the boolean value node.isUsed0 Question 1) Using tries for sorting a list of binary strings in lexicographical order. You are given a startup code with classes TreeNode, MyTrie, TestTry. TreeNode is a node in the trie, MyTrie stores the trie as in Figure 2 and TestTry is a sample code that does some tests for class MyTrie. TreeNode and TestTry must not be changed, while you can change class MyTrie. You are allowed to add extra methods or member variables, and add code to given methods, but the signature of the given methods should not be changed. Most methods of MyTrie are not implemented and implementing them is part of your task. Part 1A) (55 marks 25+15+15) Implement the missing code in the following methods of class myTrie public boolean insert (String s): This method "inserts" a string in the trie by adding appropriate nodes to the tree to represent the string. Note that the node representing the given string must have the flag "isUsed" set to true, while intermediate nodes that do not represent any of the strings inserted into the tree will have flag "isUsed" equal to false. If the string being inserted is already present in the trie, return false, otherwise insert the string and return true. public boolean search(String s): Returns true if and only if the string is "stored" in the trie. public void printStringsInLexicoOrderO This method will print, in lexicographical order, all strings that are "stored" in the trie. This printing can be done by an appropriate tree traversal. Note that it may be useful to do some of this traversal recursively, and you are free to add another private auxiliary recursive method that will do most of this traversal/printing Important: This method should be efficient and run in Theta(N) where N is the sum of the lengths of all the binary strings stored in the trie While you are testing and implementing, you may find useful to check that your tree is being built in the right way. For this purpose we provide the method printlnOrder0 that prints the tree using an inorder traversal that prints for each node the boolean value node.isUsed0