In this project, you will implement a Binary Tree and then write a player for Myopic Col on trees. Your version of a Binary Tree will be called PureBinaryTree. This will have a recursive structure, similar to our Linked List implementation.

Part 0, 0 points: Each binary tree will have exactly three fields: a value at this node (of whatever your generic type is), and two PureBinaryTree<Type>s, which I named leftChild and rightChild. Be sure to make all three private.

Part 1, 0 points: Write a constructor that takes only one parameter (of your generic type). Similar to the linked lists, this should initialize both the recursive fields to null.

Part 2, 0 points: Let's write the toString in parts. I have two versions, one which takes one parameter, and the other (standard) version which has none. Let's do the one-parameter version first. The parameter will indicate how much this tree is indented when printed out. Add the following method: (you'll need to import java.lang.*)

public String toString(String indent) {
    StringBuilder builder = new StringBuilder();
    builder.append(indent + this.value + "\n");
    return builder.toString();
}

Later on, we'll modify this method later to make it print out the left and right branches of the tree as well.

Part 3, 0 points: We still need a no-parameter toString. We can write this in one line by calling the single-parameter version with the empty string as the argument.

Part 4, 5 points: Now let's add some getter and setter methods to retrieve and add values to the tree. First, write getValue, which takes no parameters and returns the value at this node. You can test with this:

PureBinaryTree<String> tree1 = new PureBinaryTree<>("Jigglypuff");
String s = tree1.getValue();
assert s.equals("Jigglypuff");
assert s.toString().contains("Jigglypuff");

PureBinaryTree<Integer> intTree1 = new PureBinaryTree<>(39);
assert intTree1.getValue() == 39;

Part 5, 5 points: Now write setValue, a void method which takes a value as the parameter and sets this node's value to that. You can check your code with this:

PureBinaryTree<String> tree1 = new PureBinaryTree<>("Jigglypuff");
String s = tree1.getValue();
assert s.equals("Jigglypuff");
tree1.setValue("Wigglytuff");
assert tree1.getValue().equals("Wigglytuff");

PureBinaryTree<Integer> intTree1 = new PureBinaryTree<>(39);
assert intTree1.getValue() == 39;
intTree1.setValue(1024);
assert intTree1.getValue() == 1024;

Part 6, 0 points: We're going to set up our trees so that we can build them like this:

PureBinaryTree<String> pokemon = new PureBinaryTree<String>("Bulbasaur");
PureBinaryTree<String> psychics = new PureBinaryTree<String>("Mewtwo");
pokemon.setLeftChild(psychics);
psychics.setLeftChild(new PureBinaryTree<String>("Kadabra"));
psychics.setRightChild(new PureBinaryTree<String>("Alakazam"));
PureBinaryTree Alakazam = psychics.getRightChild();
Alakazam.setRightChild(new PureBinaryTree<String>("Abra"));

This code creates a binary tree that looks like this:Time to build on to the tree! Implement setLeftChild, a void method which takes a PureBinaryTree<Type> as a parameter and sets the left subtree to that. You can't really test this out a bunch yet, since toString doesn't yet handle the child trees. You'll fix that in the next part.

Part 7, 10 points: It's a bit hard to get a tree to print out top-to-bottom on the console, so we'll be printing it out right-to-left. Our root will be on the far left, with it's left subtree above it and the right subtree below, each indented two spaces. (So it's a rotated and flipped version of itself.) The tree pictured above will print out like this:

    Kadabra
  Mewtwo
    Alakazam
      Abra
Bulbasaur

Let's get to updating toString so that it prints out the left-hand parts! (We'll add in the right-hand children later.) Change your method to include the new lines in this:

StringBuilder builder = new StringBuilder();
if (this.leftChild != null) {
    builder.append(this.leftChild.toString(indent + "  "));
}
builder.append(indent + this.value + "\n");

//printing the right subtree will go here

return builder.toString();

Now you should be able to see what happens after you call setLeftChild. Test this out a bunch! You should be able to build very deep trees (even with only left children). Here's some possible testing code:

PureBinaryTree<String> tree1 = new PureBinaryTree<>("Jigglypuff");
String s = tree1.getValue();
assert s.equals("Jigglypuff");
assert s.toString().contains("Jigglypuff");
tree1.setValue("Ditto");
assert tree1.getValue().equals("Ditto");
PureBinaryTree<String> tree2 = new PureBinaryTree<>("Eevee");
tree1.setLeftChild(tree2);
assert tree1.toString().contains("Eevee");
tree2.setLeftChild(new PureBinaryTree<>("Mankey"));
assert tree1.toString().contains("Mankey") && tree1.toString().contains("Eevee") && tree1.toString().contains("Ditto");

PureBinaryTree<Integer> intTree1 = new PureBinaryTree<>(39);
assert intTree1.toString().contains("39");

Part 8, 0 points: Implement setRightChild, which does nearly the same thing, but for the right-hand subtree.

Part 9, 10 points: Finish your toString method by including a part that prints contents of the right child. Add this section after it prints out the value at this node. You can kinda test this with this code, but it won't test that you have it exactly right:

PureBinaryTree<String> tree1 = new PureBinaryTree<>("Jigglypuff");
assert s.toString().contains("Jigglypuff");
tree1.setValue("Ditto");
PureBinaryTree<String> tree2 = new PureBinaryTree<>("Eevee");
tree1.setLeftChild(tree2);
assert tree1.toString().contains("Eevee");
tree2.setLeftChild(new PureBinaryTree<>("Mankey"));
assert tree1.toString().contains("Mankey") && tree1.toString().contains("Eevee") && tree1.toString().contains("Ditto");
tree1.setRightChild(new PureBinaryTree<>("Dratini"));
assert tree1.toString().contains("Dratini") && !tree2.toString().contains("Dratini");
assert tree1.toString().contains("Mankey") && tree1.toString().contains("Eevee") && tree1.toString().contains("Ditto");

PureBinaryTree<Integer> intTree1 = new PureBinaryTree<>(39);
assert intTree1.toString().contains("39");

Part 10, 0 points: Implement getLeftChild, a no-parameter method that returns the left subtree. (You don't need to worry about making a copy.)

Part 11, 0 points: Implement getRightChild, which does the analagous thing to the right subtree.

Part 12, 20 points: I know you've been looking forward to implementing a recursive method. Sorry to keep you waiting; now's the time! Write getHeight, which takes no parameters and returns the number of levels in the tree. (If there are no children, the height should be 1.) How can you determine this using two recursive calls to the two subtrees? Definitely test this thoroughly to make sure you've got it right. Here are some mild tests:

PureBinaryTree<String> tree1 = new PureBinaryTree<>("Jigglypuff");
assert tree1.getHeight() == 1;
PureBinaryTree<String> tree2 = new PureBinaryTree<>("Eevee");
assert tree2.getHeight() == 1;
tree1.setLeftChild(tree2);
assert tree1.getHeight() == 2;
tree2.setLeftChild(new PureBinaryTree<>("Mankey"));
assert tree2.getHeight() == 2;
assert tree1.getHeight() == 3;
tree1.setRightChild(new PureBinaryTree<>("Dratini"));
assert tree1.getHeight() == 3;

PureBinaryTree<String> tree3 = new PureBinaryTree<>("Jolteon");
tree2.setRightChild(tree3);
assert tree2.getHeight() == 2;
assert tree1.getHeight() == 3;
tree3.setRightChild(new PureBinaryTree<String>("Kadabra"));
assert tree3.getHeight() == 2;
assert tree2.getHeight() == 3;
assert tree1.getHeight() == 4;
tree3.getRightChild().setRightChild(new PureBinaryTree<String>("Abra"));
assert tree3.getHeight() == 3;
assert tree2.getHeight() == 4;
assert tree1.getHeight() == 5;

Part 13, 20 points: In order to check that trees are equivalent, we need an equals method. There are different ways to write this, but I strongly recommend a recursive solution. Since you'll have to test whether the subtrees are each non-null, I also recommend creating some local boolean variables such as leftSubtreesEqual to help organize your solution. Thoroughly test this to make sure it's working correctly! Here's some code:

PureBinaryTree<Integer> intTree1 = new PureBinaryTree<>(39);
assertTrue(intTree1.getValue() == 39);
intTree1.setValue(121);
assertTrue(intTree1.getValue() == 121);
assertTrue(intTree1.equals(intTree1));

PureBinaryTree<Integer> intTree1b = new PureBinaryTree<>(39);
assertTrue(!intTree1.equals(intTree1b));
intTree1b.setValue(121);
assertTrue(intTree1.equals(intTree1b));

intTree1.setLeftChild(new PureBinaryTree<Integer>(-1));
assertTrue(!intTree1.equals(intTree1b));
assertTrue(!intTree1b.equals(intTree1));
intTree1b.setLeftChild(new PureBinaryTree<Integer>(-2));
assertTrue(!intTree1.equals(intTree1b));
assertTrue(!intTree1b.equals(intTree1));
intTree1b.getLeftChild().setValue(-1);
assertTrue(intTree1.equals(intTree1b));

intTree1.setRightChild(new PureBinaryTree<Integer>(10));
assertTrue(!intTree1.equals(intTree1b));
assertTrue(!intTree1b.equals(intTree1));
intTree1b.setRightChild(new PureBinaryTree<Integer>(11));
assertTrue(!intTree1.equals(intTree1b));
assertTrue(!intTree1b.equals(intTree1));
intTree1b.getRightChild().setValue(10);
assertTrue(intTree1.equals(intTree1b));

intTree1.getRightChild().setLeftChild(new PureBinaryTree<Integer>(5));
assertTrue(!intTree1.equals(intTree1b));
assertTrue(!intTree1b.equals(intTree1));
intTree1b.getRightChild().setLeftChild(new PureBinaryTree<Integer>(4));
assertTrue(!intTree1.equals(intTree1b));
assertTrue(!intTree1b.equals(intTree1));
intTree1b.getRightChild().getLeftChild().setValue(5);
assertTrue(intTree1.equals(intTree1b));

intTree1.setLeftChild(null);
assertTrue(!intTree1.equals(intTree1b));
assertTrue(!intTree1b.equals(intTree1));
intTree1b.setLeftChild(null);
assertTrue(intTree1.equals(intTree1b));

Part 14, 0 points: Let's test your code out during actual game play. To compile and run the code locally, you'll need these:

• Abstract CG class: download and compile CombinatorialGame.java.
• Player classes: Player.java and RandomPlayer.java.
• Abstract class for generation of game states: PositionFactory.java.
• Referee: Referee.java.

Part 15, 0 points: The game for this project is Tree Myopic Col. If you want to compile this on your own, you'll need these things: TreeMyopicCol.java, RefereeWithSwingDisplay.java, SwingDisplayable.java, and TreeMyopicColPanel.java.

Part 16, 20 points: Create your own player, TreeMyopicColPlayer.java player. Start off by getting getMove to always return a legal move. I highly recommend trying to write this so that it's recursive. Please ask for help if you're having a hard time organizing that! Remember:

• Your player should only directly invoke the PureBinaryTree methods assigned here. I'll be testing your player with my own copy of PureBinaryTree.java, so if you call other methods, your player won't compile and you won't earn any points for it.
• Don't use randomness in your player. (Randomness is a really powerful tool. If you're interested in writing a player that uses randomness, we should definitely talk after this course is finished!)
• Don't call the getOptions method.
• Make sure your player decides its move in a reasonable amount of time. (If it runs too long, I'll have to kill the process. Exponential-time players are probably not going to earn points.)
• Add a toString method if you want to give your player an interesting name. (Highly recommended.)

You can set up a competition with a random player like this:

int minHeight = 3;
int maxHeight = 4;
double childProbability = .75;
double colorProbability = .15;

PositionFactory<TreeMyopicCol> factory = new TreeMyopicCol.PositionBuilder(minHeight, maxHeight, childProbability, colorProbability);
Player<TreeMyopicCol> me = new TreeMyopicColPlayer();
Player<TreeMyopicCol> random = new RandomPlayer<TreeMyopicCol>();
Referee<TreeMyopicCol> ref = new Referee<>(me, random, factory);

ref.call();
ref.gauntlet(10000);

That's likely not super useful because it's hard to read the string output of the game as it's being played. I made a graphical display for the game, that you can use like this:

int minHeight = 3;
int maxHeight = 4;
double childProbability = .75;
double colorProbability = .15;

PositionFactory<TreeMyopicCol> factory = 
    new TreeMyopicCol.PositionBuilder(minHeight, maxHeight, childProbability, colorProbability);
Player<TreeMyopicCol> me = new TreeMyopicColPlayer();
Player<TreeMyopicCol> random = new RandomPlayer<TreeMyopicCol>();
Referee<TreeMyopicCol> ref = new Referee<>(me, random, factory);
RefereeWithSwingDisplay<TreeMyopicCol> guiRef = 
    new RefereeWithSwingDisplay<>(me, random, factory);

guiRef.call();
//the next line is not a mistake
ref.gauntlet(10000);

Part 17, 10 points: Modify your strategy so that your player does well against my random player. You will earn points depending on how often you win in my tests. Warning: I won't tell you the parameters of those tests. I recommend chatting with other teams about the factory parameters they're using and going with the hardest ones. Important: do not copy code from any outside sources, but:

• It's okay to search online for strategies and info about this game, as long as you're not getting code (in any programming language) or pseudocode.
• It's okay to talk to other people about strategies so long as you're not sharing code.
• It's okay to challenge me to a game if that would help!

Here's how many points you earn based on how your player does when I test it:

• Win ≥45%: 5 points
• Win ≥79%: 10 points
• Win ≥93%: 15 points
• Win ≥98%: 20 points

Submitting your Project:

The files I'm looking for in this project are:

• PureBinaryTree.java
• TreeMyopicColPlayer.java

Please make sure to remove scaffolding from your code so that it doesn't print a ton when executed. Your team name is your username if you're working alone or your members' last names with "And" between them if you're working with a teammate. (For example, alone my teamname would be "kburke", but when working with Stacey Stock it would be "burkeAndStock".) Put completed working files you have in a folder named <YourTeamName>Project7, then zip the folder and upload the resulting .zip file to the assignment's canvas page so I can grade it. (E.g., for me: kburkeProject7.zip or burkeAndStockProject7.zip.) If you do it before the deadline and want me to run it through my tester to see how it does against the random players, send me a message and I'll do it. If you upload it after the deadline, please send me a message so I can grade it ASAP. Please please please name the folder correctly, then zip it; don't rename the zip file, or you'll have to resubmit and may incur a lateness penalty.