public class LinkedList { Item head; Item tail; public LinkedList() { head = null; tail = null; } // Add an item to the end of the list public void add(Item x) { if (tail == null) { tail = x; head = x; } else { tail.next = x; x.previous = tail; tail = x; } } // Remove the given item from the list public void remove(Item x) { if (x == head) { if (x == tail) { head = tail = null; } else { head = x.next; head.previous = null; } } else { if (x == tail) { tail = x.previous; tail.next = null; } else { x.previous.next = x.next; x.next.previous = x.previous; } } } // Return a string representation of the list public String toString() { if (head == null) return "[EMPTY]"; String s = "[H:"; Item currentItem = head; while (currentItem != null) { s += currentItem.data; if (currentItem != tail) s += "]["; currentItem = currentItem.next; } return s + ":T]"; } // Add up the total data in the list public int totalData() { if (head == null) return 0; int total = 0; Item currentItem = head; while (currentItem != null) { total += currentItem.data; currentItem = currentItem.next; } return total; } // Add up the total data in the list using recursion public int totalDataRecursive() { return totalDataRecursive(head); } // Add up the total data in the list using recursion private int totalDataRecursive(Item start) { if (start == null) return 0; return start.data + totalDataRecursive(start.next); } // Return a new linked list containing all items with odd data from this list using recursion public LinkedList oddItems() { return oddItems(head); } // Return all items with odd data in the list using recursion private LinkedList oddItems(Item start) { if (start == null) return new LinkedList(); LinkedList result = oddItems(start.next); if (start.data %2 != 0) result.add(new Item(start.data)); return result; } // Return all items with odd data in the list using recursion private LinkedList oddItems2(Item startItem, LinkedList resultList) { if (startItem == null) return resultList; if (startItem.data %2 != 0) resultList.add(new Item(startItem.data)); return oddItems2(startItem.next, resultList); } // Return a new linked list containing all common elements of the two lists public LinkedList inCommon(LinkedList aList) { return inCommon(this.head, aList.head, new LinkedList()); } // Return all items which are common between the two lists private LinkedList inCommon(Item start1, Item start2, LinkedList result) { if ((start1 == null) || (start2 == null)) return result; if (contains(start1,start2.data)) result.add(new Item(start2.data)); return inCommon(start1, start2.next, result); } // Return a boolean indicating whether or not the list contains a given item's data public boolean contains(Item startItem, byte data) { if (startItem == null) return false; if (startItem.data == data) return true; else return contains(startItem.next, data); } public boolean isInIncreasingOrder() { return false; //. Replace this code with your own } } 

public class SortedListTestProgram { public static void main(String args[]) { LinkedList list = new LinkedList(); System.out.println(" Here is the list: " + list); System.out.println("The list is sorted: " + list.isInIncreasingOrder()); list = new LinkedList(); list.add(new Item(14)); System.out.println(" Here is the list: " + list); System.out.println("The list is sorted: " + list.isInIncreasingOrder()); list = new LinkedList(); list.add(new Item(14)); list.add(new Item(21)); System.out.println(" Here is the list: " + list); System.out.println("The list is sorted: " + list.isInIncreasingOrder()); list = new LinkedList(); list.add(new Item(21)); list.add(new Item(14)); System.out.println(" Here is the list: " + list); System.out.println("The list is sorted: " + list.isInIncreasingOrder()); list = new LinkedList(); list.add(new Item(14)); list.add(new Item(21)); list.add(new Item(23)); list.add(new Item(10)); System.out.println(" Here is the list: " + list); System.out.println("The list is sorted: " + list.isInIncreasingOrder()); list = new LinkedList(); list.add(new Item(14)); list.add(new Item(21)); list.add(new Item(23)); list.add(new Item(45)); list.add(new Item(76)); list.add(new Item(95)); list.add(new Item(98)); System.out.println(" Here is the list: " + list); System.out.println("The list is sorted: " + list.isInIncreasingOrder()); } }

import java.util.ArrayList; public class BinaryTree { private String data; private BinaryTree leftChild; private BinaryTree rightChild; public BinaryTree() { data = null; leftChild = null; rightChild = null; } public BinaryTree(String d) { data = d; leftChild = new BinaryTree(); rightChild = new BinaryTree(); } public BinaryTree(String d, BinaryTree left, BinaryTree right) { data = d; leftChild = left; rightChild = right; } public String getData() { return data; } public BinaryTree getLeftChild() { return leftChild; } public BinaryTree getRightChild() { return rightChild; } public void setData(String d) { data = d; } public void setLeftChild(BinaryTree left) { leftChild = left; } public void setRightChild(BinaryTree right) { rightChild = right; } public ArrayList leafData() { ArrayList result = new ArrayList(); if (data != null) { if ((leftChild.data == null) && (rightChild.data == null)) result.add(data); result.addAll(leftChild.leafData()); result.addAll(rightChild.leafData()); } return result; } public int height() { if (data == null) return 0; return 1 + Math.max(leftChild.height(), rightChild.height()); } public boolean contains(String s){ return false; //Replace this code with your own } public boolean isTheSameAs(BinaryTree t) { return false; //Replace this code with your own } } 

public class Item { public byte data; public Item previous; public Item next; public Item(int d) { data = (byte)d; previous = null; next = null; } }

public class BinaryTreeTestProgram { public static void main(String[] args) { BinaryTree root; root = new BinaryTree("A", new BinaryTree("B", new BinaryTree("C", new BinaryTree("D"), new BinaryTree("E", new BinaryTree("F", new BinaryTree("G"), new BinaryTree("I")), new BinaryTree("H"))), new BinaryTree("J", new BinaryTree("K", new BinaryTree(), new BinaryTree("L", new BinaryTree(), new BinaryTree("M"))), new BinaryTree("N", new BinaryTree(), new BinaryTree("O")))), new BinaryTree("P", new BinaryTree("Q"), new BinaryTree("R", new BinaryTree("S", new BinaryTree("T"), new BinaryTree()), new BinaryTree("U")))); System.out.println("Tree Height = " + root.height()); System.out.println("Tree Leaves = " + root.leafData()); } } 

public class BinaryTreeTestProgram2 { public static void main(String[] args) { BinaryTree tree1, tree2, tree3, tree4, tree5; tree1 = new BinaryTree("A", new BinaryTree("B", new BinaryTree("C", new BinaryTree("D"), new BinaryTree("E", new BinaryTree("F", new BinaryTree("G"), new BinaryTree("I")), new BinaryTree("H"))), new BinaryTree("J", new BinaryTree("K", new BinaryTree(), new BinaryTree("L", new BinaryTree(), new BinaryTree("M"))), new BinaryTree("N", new BinaryTree(), new BinaryTree("O")))), new BinaryTree("P", new BinaryTree("Q"), new BinaryTree("R", new BinaryTree("S", new BinaryTree("T"), new BinaryTree()), new BinaryTree("U")))); tree2 = new BinaryTree("A", new BinaryTree("B", new BinaryTree("C", new BinaryTree("D"), new BinaryTree("E", new BinaryTree("F", new BinaryTree("Z"), //different letter here new BinaryTree("I")), new BinaryTree("H"))), new BinaryTree("J", new BinaryTree("K", new BinaryTree(), new BinaryTree("L", new BinaryTree(), new BinaryTree("M"))), new BinaryTree("N", new BinaryTree(), new BinaryTree("O")))), new BinaryTree("P", new BinaryTree("Q"), new BinaryTree("R", new BinaryTree("S", new BinaryTree("T"), new BinaryTree()), new BinaryTree("U")))); tree3 = new BinaryTree("A", new BinaryTree("B", new BinaryTree("C", new BinaryTree("D"), new BinaryTree("E", new BinaryTree("F", new BinaryTree("G"), new BinaryTree("I")), new BinaryTree("H"))), new BinaryTree()), // "J" tree removed new BinaryTree("P", new BinaryTree("Q"), new BinaryTree("R", new BinaryTree("S", new BinaryTree("T"), new BinaryTree()), new BinaryTree("U")))); tree4 = new BinaryTree("A", new BinaryTree("B", new BinaryTree("C", new BinaryTree("D"), new BinaryTree("E", new BinaryTree("F", new BinaryTree("G"), new BinaryTree("I")), new BinaryTree("H"))), new BinaryTree("J", new BinaryTree("K", new BinaryTree(), new BinaryTree("L", new BinaryTree(), new BinaryTree("M"))), new BinaryTree("N", new BinaryTree(), new BinaryTree("O")))), new BinaryTree("P", new BinaryTree("Q"), new BinaryTree("R", new BinaryTree("S", new BinaryTree("T"), new BinaryTree()), new BinaryTree()))); // "U" tree removed tree5 = new BinaryTree("A", new BinaryTree(), new BinaryTree()); // only single node tree System.out.println("Tree 1 is the same as Tree 1 = " + tree1.isTheSameAs(tree1)); // true System.out.println("Tree 1 is the same as Tree 2 = " + tree1.isTheSameAs(tree2)); // false System.out.println("Tree 1 is the same as Tree 3 = " + tree1.isTheSameAs(tree3)); // false System.out.println("Tree 1 is the same as Tree 4 = " + tree1.isTheSameAs(tree4)); // false System.out.println("Tree 1 is the same as Tree 5 = " + tree1.isTheSameAs(tree5)); // false System.out.println("Tree 5 is the same as Tree 1 = " + tree5.isTheSameAs(tree1)); // false System.out.println("Tree 5 is the same as Tree 5 = " + tree5.isTheSameAs(tree5)); // true } } 

1) Consider the LinkedList class provided in the tutorial Write the code for the instance method in the LinkedList class called islnincreasingOrder) which returns a boolean indicating whether or not the data in the list is in increasing order i. The method must be recursive. It makes sense to have a directly recursive method that takes, as a parameter, an Item in the list and checks the remaining items after it. ii. You will need to check to make sure that there is at least one Item in the list before calling the recursive method Below are some examples and the expected results. Use the SortedListTestProgram to test your results to make sure that your method works prop null TRUE null null TRUE 14 null TRUE 14 21 null null null FALSE 21 14 null null FALSE 14 21 23 10 null nul TRUE 14 21 23 45 76 95 98 null