I need help implementing my printPathsBackToTheRoot() (method 5) and my method 7, which makes the class Iterable to use for each loop to print the in-order traversal of the cities. All information/text files are given. Please make sure the two test cases pass regarding these methods.

printPathsBackToTheRoot()

This method returns all node-to-root paths. The nodes should be considered in the elevator order, as described in Method 1. You can simply use a queue like Method 3 for this. First, you should enqueue the left child and then the right child. For the example tree, this method should return the following string. The parent field inside every node will help you now to easily climb up to the root. Use newline characters to introduce newlines in the return string. Output:

Jacksonville Miami Jacksonville Chicago Jacksonville Omaha Miami Jacksonville Boston Chicago Jacksonville NYC Chicago Jacksonville Orlando Omaha Miami Jacksonville Atlanta NYC Chicago Jacksonville Tampa NYC Chicago Jacksonville

Method 7

Your final task is to make the class BinaryTreeOfOz iterable so that one can use a for-each loop to traverse the whole tree. In this case, the traversal must be in-order. See the supplied code for more insights. For the above tree B, when the following for-each loop is used:

for(String s : B)

System.out.print(s + " ");

Output:

......

JAVA CLASS FILES(3)

BinaryTreeOfOz.java (1)

package hw4; // do not delete import java.io.*; import java.util.*; import stacksandqueues.*; //do not delete this; use stacks and queues from this package if you need to public class BinaryTreeOfOz implements Iterable { //-------------Modify accordingly------------------------// private static class Node { final private City info; private Node left, right; public Node(City info, Node left, Node right) { this.info = info; this.left = left; this.right = right; } public String getCity() { return info.getCityName(); } public String getInfo() { return info.toString(); } public String toString() { return info.toString(); } } //------------------------------------ Node root; private int size; //------------------------------------- public boolean isEmpty() { return size == 0; } // Method 1: constructs a binary tree by reading information from an input file public BinaryTreeOfOz(String inputFile) throws IOException { // create file and scanner to read file File file = new File(inputFile); Scanner scanner = new Scanner(file); while (scanner.hasNextLine()) { String line = scanner.nextLine(); String[] parts = line.split(" "); String cityName = parts[0]; String cityColor = parts[1]; City city = new City(cityName, cityColor); Node newNode = new Node(city, null, null); if (root == null) { root = newNode; } else { Node current = root; String path = parts[2]; for (int i = 0; i < path.length() - 1; i++) { if (path.charAt(i) == 'L') current = current.left; else current = current.right; } if (path.charAt(path.length() - 1) == 'L') current.left = newNode; else current.right = newNode; } size++; } scanner.close(); } // end BinaryTreeOfOz(String inputFile) // Method 2: counts the # of triChromatic groups in the tree public int countTriChromaticGroups() { return recursiveChromaticGroups(root); } private int recursiveChromaticGroups(Node n) { if (n == null) return 0; int count = 0; if (n.left != null && n.right != null) { String currentColor = n.info.getCityColor(); String leftColor = n.left.info.getCityColor(); String rightColor = n.right.info.getCityColor(); if (!currentColor.equals(leftColor) && !currentColor.equals(rightColor) && !leftColor.equals(rightColor)) count++; } count += recursiveChromaticGroups(n.left) + recursiveChromaticGroups(n.right); return count; } // Method 3: returns the reverse elevator order traversal of the tree public String getReverseElevatorOrder() { StringBuilder str = new StringBuilder(); // complete if (root == null) { return str.toString(); } Queue queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { Node node = queue.poll(); str.append(node.getCity()).append(" "); if (node.right != null) { queue.offer(node.right); } if (node.left != null) { queue.offer(node.left); } } return str.toString().trim(); } // Method 4: computes the height of the tree public int computeHeight() { return recursiveHeight(root); } private int recursiveHeight(Node node) { if (node == null) { return -1; // Base case: height of an empty tree is -1 } int leftHeight = recursiveHeight(node.left); int rightHeight = recursiveHeight(node.right); return Math.max(leftHeight, rightHeight) + 1; } // Method 5: returns the paths to the root public String printPathsBackToTheRoot() { StringBuilder str = new StringBuilder(); //complete return str.toString(); } private Node findFirstCommonCity(Node node, String cityA, String cityB) { if (node == null) { return null; } if (node.getCity().equals(cityA) || node.getCity().equals(cityB)) { return node; } Node left = findFirstCommonCity(node.left, cityA, cityB); Node right = findFirstCommonCity(node.right, cityA, cityB); if (left != null && right != null) { return node; // Current node is the first common city } return (left != null) ? left : right; } // The 7th item; you need create an iterator for this class // When a for-each loop is used to traverse an object of this class, // at every iteration, a string representation of the current node can be obtained public Iterator iterator() { return new BinaryTreeOfOz.BinaryTreeOfOzIterator(this); } public static class BinaryTreeOfOzIterator implements Iterator { public BinaryTreeOfOzIterator(BinaryTreeOfOz T) { } public boolean hasNext() { return false; // dummy statement } public String next() { return ""; } } }

TestBinaryTreeOfOz.java (2)

package hw4; // do not delete import java.io.*; public class TestBinaryTreeOfOz { public static String squeeze(String s) { if( s == null ) return ""; StringBuilder str = new StringBuilder(); for(int i = 0; i < s.length(); i++) if( Character.isJavaIdentifierPart( s.charAt(i) ) ) str.append( s.charAt(i) ); return str.toString(); } public static String removeSpace(String s) { if( s == null ) return ""; StringBuilder str = new StringBuilder(); for(int i = 0; i < s.length(); i++) if( s.charAt(i) != ' ') str.append( s.charAt(i) ); return str.toString(); } public static void main(String[] args) throws IOException { int score = 0; ///======================= Testing HW4-Tree2.txt ============================// { System.out.println("Testing HW4-Tree1.txt "); try { BinaryTreeOfOz B = new BinaryTreeOfOz("src/hw4/Trees/HW4-Tree1.txt"); B.computeHeight();// a dummy statement to eliminate warnings } catch (Exception e) { System.out.println("Your constructor is not working correctly! Please fix it. Without this, your code cannot be tested. "); System.out.println("if the other methods are implemented correctly. "); } BinaryTreeOfOz B = new BinaryTreeOfOz("src/hw4/Trees/HW4-Tree1.txt"); score += 5; System.out.println(); if (B.countTriChromaticGroups() == 2) score += 10; else { System.out.println("countTriChromaticGroups() failed"); System.out.println("Your output: " + B.countTriChromaticGroups() + " "); } if (squeeze(B.getReverseElevatorOrder()).equals("JacksonvilleChicagoMiamiNYCBostonOmahaTampaAtlantaOrlando")) score += 5; else { System.out.println("getReverseElevatorOrder() failed"); System.out.println("Your output: " + B.getReverseElevatorOrder() + " "); } if (B.computeHeight() == 3) score += 5; else { System.out.println("computeHeight() failed"); System.out.println("Your output: " + B.computeHeight() + " "); } if (squeeze(B.printPathsBackToTheRoot()).equals(squeeze("Jacksonville Miami Jacksonville Chicago Jacksonville Omaha Miami Jacksonville Boston Chicago Jacksonville NYC Chicago Jacksonville Orlando Omaha Miami Jacksonville Atlanta NYC Chicago Jacksonville Tampa NYC Chicago Jacksonville"))) score += 10; else { System.out.println("printPathsBackToTheRoot() failed"); System.out.println("Your output: " + B.printPathsBackToTheRoot() + " "); } if (squeeze(B.findFirstCommonCity("Boston", "Tampa")).equals("Chicago")) ; else { System.out.println("findFirstCommonCity(\"Boston\", \"Tampa\") failed"); System.out.println("Your output: " + B.findFirstCommonCity("Boston", "Tampa") + " "); } if (squeeze(B.findFirstCommonCity("Tampa", "NYC")).equals("NYC")) score += 10; else { System.out.println("findFirstCommonCity(\"Tampa\", \"NYC\") failed"); System.out.println("Your output: " + B.findFirstCommonCity("Tampa", "NYC") + " "); } StringBuilder str = new StringBuilder(); for(String s : B) { // should work when the nested iterator class has been completed str.append(s); } if(removeSpace(str.toString()).equals("")) score += 5; else { System.out.println("for-each loop did not work as expected!"); System.out.println("str contains: " + str.toString()); } } ///=================================================================// ///======================= Testing HW4-Tree2.txt ============================// { System.out.println("Testing HW4-Tree2.txt "); try { BinaryTreeOfOz B = new BinaryTreeOfOz("src/hw4/Trees/HW4-Tree2.txt"); B.computeHeight();// a dummy statement to eliminate warnings } catch (Exception e) { System.out.println("Your constructor is not working correctly! Please fix it. Without this, your code cannot be tested even "); System.out.println("if the other methods are implemented correctly. "); } BinaryTreeOfOz B = new BinaryTreeOfOz("src/hw4/Trees/HW4-Tree2.txt"); score += 5; if (B.countTriChromaticGroups() == 3) score += 10; else { System.out.println("countTriChromaticGroups() failed"); System.out.println("Your output: " + B.countTriChromaticGroups() + " "); } if (squeeze(B.getReverseElevatorOrder()).equals("C1C3C2C5C4C9C8C7C6C11C10C12")) score += 5; else { System.out.println("getReverseElevatorOrder() failed"); System.out.println("Your output: " + B.getReverseElevatorOrder() + " "); } if (B.computeHeight() == 5) score += 5; else { System.out.println("computeHeight() failed"); System.out.println("Your output: " + B.computeHeight() + " "); } if (squeeze(B.printPathsBackToTheRoot()).equals(squeeze("C1 C2C1 C3C1 C4C3C1 C5C3C1 C6C4C3C1 C7C4C3C1 C8C5C3C1 C9C5C3C1 C10C6C4C3C1 C11C8C5C3C1 C12C10C6C4C3C1"))) score += 10; else { System.out.println("printPathsBackToTheRoot() failed"); System.out.println("Your output: " + B.printPathsBackToTheRoot() + " "); } if (squeeze(B.findFirstCommonCity("C12", "C9")).equals("C3")) ; else { System.out.println("findFirstCommonCity(\"C12\", \"C9\") failed"); System.out.println("Your output: " + B.findFirstCommonCity("C12", "C9") + " "); } if (squeeze(B.findFirstCommonCity("C2", "C11")).equals("C1")) score += 10; else { System.out.println("findFirstCommonCity(\"C2\", \"C11\") failed"); System.out.println("Your output: " + B.findFirstCommonCity("C2", "C11") + " "); } StringBuilder str = new StringBuilder(); for(String s : B) { // should work when the nested iterator class has been completed str.append(s); } if(removeSpace(str.toString()).equals("")) score += 5; else { System.out.println("for-each loop did not work as expected!"); System.out.println("str contains: " + str.toString()); } } ///=================================================================// System.out.println("Score: " + score); } }

City.java (3)

package hw4; // do not delete public class City { private final String name, color; public City(String name, String color) { this.name = name; this.color = color; } public String getCityColor() { return color; } public String getCityName() { return name; } public String toString() { return "<" + name + "," + color + ">"; } }

JAVA TEXT FILES(2)

HW4-Tree1.txt

Jacksonville Magenta Miami Yellow L Chicago DarkGreen R Omaha Purple LL Boston Yellow RL NYC Magenta RR Orlando Amber LLR Atlanta Pink RRL Tampa Magenta RRR

HW4-Tree2.txt

C1 Red C2 Green L C3 Yellow R C4 Red RL C5 Yellow RR C6 Green RLL C7 Blue RLR C8 Orange RRL C9 Black RRR C10 Green RLLL C11 Purple RRLL C12 Red RLLLL