How can I implement my printPathsBackToTheRoot() method to get the expected output using a queue like method 3 as stated in the description below? This method should pass the test case when implemented.

 

The printPathsBackToTheRoot() 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 climb up to the root quickly. Use newline characters to introduce newlines in the return string.

 

 

Expected 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

 

 

 

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 parent;

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;
}
newNode.parent = current;
}
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 sb = new StringBuilder();
// complete using queue to get expected output
Queue Q = new LinkedList<>();

while(!Q.isEmpty()) {

}
return sb.toString(); // trim the trailing newline
}

// Method 6: finds out the first common city for two cities
public String findFirstCommonCity(String cityA, String cityB) {
// complete
Node commonCity = findFirstCommonCity(root, cityA, cityB);
return (commonCity != null) ? commonCity.getCity() : null;
}

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
public Iterator iterator() {
return new BinaryTreeOfOz.BinaryTreeOfOzIterator(this);
}

public static class BinaryTreeOfOzIterator implements Iterator {
private final Stack stack;

public BinaryTreeOfOzIterator(BinaryTreeOfOz T) {
stack = new Stack<>();
Node current = T.root;
while (current != null) {
stack.push(current);
current = current.left;
}
}

public boolean hasNext() {
return !stack.isEmpty();
}

public String next() {
if (!hasNext()) {
throw new NoSuchElementException();
}

Node node = stack.pop();
Node current = node.right;
while (current != null) {
stack.push(current);
current = current.left;
}

return node.getInfo();
}
}
}


 

 

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\n");
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.\nWithout this, your code cannot be tested. ");
System.out.println("if the other methods are implemented correctly.\n\n");
}

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() + "\n");
}

if (squeeze(B.getReverseElevatorOrder()).equals("JacksonvilleChicagoMiamiNYCBostonOmahaTampaAtlantaOrlando"))
score += 5;
else {
System.out.println("getReverseElevatorOrder() failed");
System.out.println("Your output: " + B.getReverseElevatorOrder() + "\n");
}

if (B.computeHeight() == 3)
score += 5;
else {
System.out.println("computeHeight() failed");
System.out.println("Your output: " + B.computeHeight() + "\n");
}

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() + "\n");
}

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") + "\n");
}

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") + "\n");
}

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\n");
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.\nWithout this, your code cannot be tested even ");
System.out.println("if the other methods are implemented correctly.\n\n");
}

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() + "\n");
}

if (squeeze(B.getReverseElevatorOrder()).equals("C1C3C2C5C4C9C8C7C6C11C10C12"))
score += 5;
else {
System.out.println("getReverseElevatorOrder() failed");
System.out.println("Your output: " + B.getReverseElevatorOrder() + "\n");
}

if (B.computeHeight() == 5)
score += 5;
else {
System.out.println("computeHeight() failed");
System.out.println("Your output: " + B.computeHeight() + "\n");
}

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() + "\n");
}

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") + "\n");
}

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") + "\n");
}

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