Program 6 Trees Complete the program, Program6Template, we began in class so that the program displays a menu from which the user can select that the nodes be out put in ascending, descending, or NRL order.To do this, add the below three shows-all methods to the data structure class, and add three private methods that they invoke to perform the output. 1. Output all student nodes in ascending order(showAllAscending) 2. Output all the student nodes in descending order(showAllDescending) 3. Output all the student nodes in NRL order(showAllHRL) public class BinaryTree { TreeNode root; public BinaryTree() { root = null; } public boolean insert(Listing newListing) { TreeNodeWrapper p = new TreeNodeWrapper(); TreeNodeWrapper c = new TreeNodeWrapper(); TreeNode n = new TreeNode(); if(n == null) // out of memory return false; else // insert the node { n.node = newListing.deepCopy(); // copy the node as a leaf node n.lc = null; n.rc = null; if(root == null) // tree is empty { root = n; } else { findNode(newListing.getKey(), p, c ); // find the new node's parent if(newListing.getKey().compareTo(p.get().node.getKey( )) < 0) // insert at right p.get().lc = n; else p.get().rc = n; } return true; } } //end insert method public Listing fetch(String targetKey) { boolean found; TreeNodeWrapper p = new TreeNodeWrapper(); TreeNodeWrapper c = new TreeNodeWrapper(); found = findNode(targetKey, p, c); // insert the new leaf node if(found == true) return c.get().node.deepCopy(); else return null; }// end of fetch method public boolean delete(String targetKey) { boolean found; TreeNodeWrapper p = new TreeNodeWrapper(); TreeNodeWrapper c = new TreeNodeWrapper(); TreeNode largest; TreeNode nextLargest; found = findNode(targetKey, p, c); if(found == false) // node not found return false; else { if(c.get().lc == null && c.get().rc == null) // case 1: deleted node has no children { if(p.get().lc == c.get()) // deleted node is a left child p.get().lc = null; else // deleted node is a right child p.get().rc = null; }// end case 1 else if(c.get().lc == null || c.get().rc == null) // case 2: delete node has one child { if(p.get().lc == c.get()) //deleted node is a left child { if(c.get().lc != null) // deleted node has a left child p.get().lc = c.get().lc; else p.get().lc = c.get().rc; } else // deleted node is a right child { if(c.get().lc != null) // deleted node has a left child p.get().rc = c.get().lc; else p.get().rc = c.get().rc; } }// end case 2 else // case 3: deleted node has two children { nextLargest = c.get().lc; largest = nextLargest.rc; if(largest != null) // left child of deleted node has a right subtree { while(largest.rc != null) // move down the right edge of right subtree { nextLargest = largest; largest = largest.rc; } c.get().node = largest.node; // "copy" largest node's info into deleted node nextLargest.rc = largest.lc; // save left subtree of largest node } else // left child of deleted node does not have a right subtree { nextLargest.rc = c.get().rc; // save the right subtree of the deleted node if(p.get().lc == c.get()) //deleted node is a left child p.get().lc = nextLargest; // deleted node's parent jumps around deleted node else // deleted node is a right child p.get().rc = nextLargest; // deleted node's parent jumps around deleted node } }// end of case 3 return true; } }// end of delete method public boolean update(String targetKey, Listing newListing) { if(delete(targetKey) == false) return false; else if(insert(newListing) == false) return false; return true; }//end of update public class TreeNode { private Listing node; private TreeNode lc; private TreeNode rc; public TreeNode() { } }// end of class TreeNode private boolean findNode(String targetKey, TreeNodeWrapper parent, TreeNodeWrapper child) { parent.set(root); child.set(root); if(root == null) // tree is empty return true; while(child.get( ) != null) { if(child.get( ).node.compareTo(targetKey) == 0) // node found return true; else { parent.set(child.get( )); if(targetKey.compareTo(child.get( ).node.getKey( )) < 0) child.set(child.get( ).lc); else child.set(child.get( ).rc); } }// end while return false; } // end of findNode public class TreeNodeWrapper { TreeNode treeRef = null; public TreeNodeWrapper() { } public TreeNode get() { return treeRef; } public void set(TreeNode t) { treeRef = t; } }// end of class TreeNodeWrapper public void showAllLNR() { outputLNR(root); } private void outputLNR(TreeNode r) { if(r == null) // base case { return; } outputLNR(r.lc); // rp1, output the entire left subtree System.out.println(r.node); outputLNR(r.rc); // rp2, output the entire right subtree } }//end class BinaryTree package program6template; public class Listing { private String name; // key field private String address; private String number; public Listing(String n, String a, String num ) { name = n; address = a; number = num; } public String toString( ) { return("Name is " + name + " Address is " + address + " Number is " + number + " "); } public Listing deepCopy( ) { Listing clone = new Listing(name, address, number); return clone; } public int compareTo(String targetKey) { return(name.compareTo(targetKey)); } public void setAddress(String a) // coded to demonstrate encapsulation { address = a; } public String getKey() { return name; } }// end of class Listing public class Program6Template { public static void main(String[] args) { BinaryTree bTree = new BinaryTree(); Listing l; Listing listing1 = new Listing("Ann", "1st Avenue", "111 1111"); Listing listing2 = new Listing("Bill", "2nd Avenue", "222 2222" ); Listing listing3 = new Listing("Carol", "3rd Avenue", "333 3333"); Listing listing4 = new Listing("Mike", "4th Avenue", "444 4444"); Listing listing5 = new Listing("Pat", "5th Avenue", "555 5555"); Listing listing6 = new Listing("Sally", "6th Avenue", "666 6666"); Listing listing7 = new Listing("Vick", "7th Avenue", "888 8888"); Listing listing8 = new Listing("Will", "8th Avenue", "999 9999"); Listing listing9 = new Listing("Xray", "9th Avenue", "101 0101"); Listing listing10 = new Listing("Zeek", "10th Avenue", "121 2121"); // insert and fetch nodes bTree.insert(listing9); bTree.insert(listing7); bTree.insert(listing10); bTree.insert(listing2); bTree.insert(listing7); bTree.insert(listing1); bTree.insert(listing4); bTree.insert(listing3); bTree.insert(listing6); bTree.insert(listing5); //System.out.println(bTree.fetch("Mike")); bTree.showAllLNR(); System.exit(0); } } Thanks and I appreciate any help.