import java.util.*; public class PoD { //============================================================================= /**  * Returns true if the game tree (binary tree) can be won  * where the last player to move wins  * @param bTree BinaryTree of interest  * @return  */   public static boolean gameCanBeWon(BinaryTree bTree) { boolean canWin; /* If both left and right subtrees are empty: - player has NO moves - is not winnable */ /* If both the left or right subtrees can be won (i.e. all positions you move to allow the other player to win), you can not win. Otherwise, you have a winning move: - move to the subtree that can not be won by your opponent - the game can be won! */ return canWin; } //============================================================================= public static void main( String [] args ) { Scanner in = new Scanner( System.in ); int i = in.nextInt(); BinaryTree newBT = makeBT(i); boolean canBeWon = gameCanBeWon(newBT); if (canBeWon) { System.out.println("You can win!"); //if you play perfectly! } else { System.out.println("You can not win this game"); //Under perfect play! } in.close(); System.out.print("END OF OUTPUT"); } public static BinaryTree makeBT(int n) { BinaryTree b; if (n>0) { b = new BinaryTree(n,makeBT(n-1),makeBT(n-2)); //System.out.println(n+":"+(n-1)+"|"+(n-2)); } else { b = new BinaryTree(0,null,null); //System.out.println(n+":null|null"); } return b; } }

Today you are going to decide who can win a game. Each node of our game tree represents a position that you can move to. We will define the winner as the last person able to make a move Winnable game If both left and right subtrees are empty, the player has NO moves and so the game can not be won (i.e. the previous player won the game If both the left or right subtrees can be won (ie. all positions you move to allow the other player to win), you can not win. Otherwise, you have a winning move: move to the subtree that can not be won by your opponent. The game can be won Details Download the ZIP files named FilesNeeded.zip for use in IntelliJ. When you are happy with your solution, upload the files into the src folder and run. You are going to finish off PoD.java to finish the gameCanBeWon method Input The main method (already completed) creates a binary tree and passes that binary tree to the gameCanBeWon method. Processing You are going to complete the details of gameCanBeWon method Details of each method and their expected parameters are described in the Javadoc comments preceding it. The method should . return true if the game can be won from that position in the game and