Task 2

Open the BinarySearchTree.java file in the task2 package. This class provides a minimal implementation of a regular (no self-balancing) binary search tree; you can only insert values in this BST.

Notice the (protected) method moodyTraversal is left to you to implement. You must implement it according to the following simple rules:

  • For any subtree, flip a coin and if the coin lands on head, visit the root before children. Otherwise, visit the root last (after having visited the children).

  • When visiting the children, flip a coin and if it lands on head, visit the left child before the right one. Otherwise, visit the right child, before visiting the left one.

You must use the provided Coin.flip() to simulate flipping a fair coin.

Open Coin.java and notice it is an enum; in case you've not seen an enum before, it is a special data type that enables for a variable to be a set of predefined constants. (Feel free to ask Google what a Java enum is). Open the Demo.main, comment out its content, add the following statements and run it to see how the Coin.flip() method works:

System.out.println(Coin.flip());
System.out.println(Coin.flip());
System.out.println(Coin.flip());
System.out.println(Coin.flip());
System.out.println(Coin.flip());

Do not change anything in the Coin.java.

Back to BinarySearchTree.java, note some class members are made protected. Please do not modify this as we need it for our solution/autograder to work properly.

You must implement moodyTraversal recursively. Once you are done with your implementation, run the provided Demo.main in the same package. The demo must print out a random permutation of the values from $1$ to $6$, inclusive. Feel free to modify the demo program to experiment with your moody traversal!

Question: Is it possible that moody-traversal generates a sequence that is similar to the output of level-order, in-order, pre-order or post-order traversal. For each, if yes please indicate how/when, if no please indicate why? Assume the question is asked about a BST that has at least three elements. Write your answer in the README.md file.