Question 1) Using tries for sorting a list of binary strings in lexicographical order. Thea startup code with classes TreeNode, MyTrie are stated below. Part 1A)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 printStringsInLexicoOrder(): 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 printInOrder() that prints the tree using an inorder traversal that prints for each node the boolean value node.isUsed() .

=====================================================================================================

Start Up Code

=====================================================================================================

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.

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 TreeNode {

private TreeNode parent;

private TreeNode leftChild;

private TreeNode rightChild;

private boolean isUsed;

public TreeNode() {

parent=null;

leftChild=null;

rightChild=null;

isUsed=false; // indicates that this is a white node (i.e. it holds a string inserted in the trie)

}

public TreeNode(TreeNode par, TreeNode left, TreeNode right, boolean used) {

parent=par;

leftChild= left;

rightChild=right;

isUsed=used;

}

public void setParent(TreeNode par) {

parent= par;

}

public void setLeftChild(TreeNode left) {

leftChild=left;

}

void setRightChild(TreeNode right) {

rightChild=right;

}

void setIsUsed(boolean used) {

isUsed=used;

}

public TreeNode getParent() {

return parent;

}

public TreeNode getLeftChild() {

return leftChild;

}

public TreeNode getRightChild() {

return rightChild;

}

public boolean getIsUsed() {

return isUsed;

}

}