Question 1) Using tries for sorting a list of binary strings in lexicographical order. Thea startup code with classes TreeNode, MyTrie are stated below.

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 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.

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;

}

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;

}

}