15-121 SPRING 2010 [CORTINA]

HOMEWORK 8 - due Tuesday, April 6

WRITTEN PROBLEMS (10 pts)

For the following problems that require recursion, your solution may not use iterative looping constructs like for and while.

  1. (1 pt)

    1. Write the preorder, inorder and postorder traversals of the binary tree shown below.

    2. A binary tree has a preorder traversal of CABDIHKMEFGJLNO and an inorder traversal of AIDBKHMCFEJNLOG. What is its postorder traversal?

  2. (1.5 pts) A binary tree is modeled using the following class: 

    public class BinaryTree<E> {
    protected BTNode<E> root;

    public void mirror() {
        // you will complete this method
    }

    ...

    protected static class BTNode<E> {
        protected E data;
        protected BTNode<E> left;
        protected BTNode<E> right;

        ...
    }
}

    Complete the method named mirror that alters the tree so that the final tree is a mirror image of the original tree. For example, if we use on this method on the tree shown on the left, we end up with the tree shown on the right. (NOTE: You will need a helper method here.)

  3. (1 pt) Recall that a full binary tree is a binary tree where each level of the tree has the maximum number of nodes possible.

    1. If the level of the root of a non-empty full binary tree is level 1, the level of the root's children is level 2, etc., how many nodes are on level i, i ≥ 1?

    2. If a non-empty full binary tree has n levels (or a height of n), how many nodes does the tree have in total? Express your answer in closed form (i.e. do not use "..." in your final answer).

    3. Prove that the number of leaves in a non-empty full binary tree is 1 more than the number of non-leaves. When you prove this, don't just show an example. Write your proof in general for ANY non-empty full binary tree.

  4. (1 pt) Write a method for the BinarySearchTree class that returns the minimum in the binary search tree using recursion. (HINT: You will need a helper method here.)

  5. (1 pt) Write a method for the BinarySearchTree class that returns the minimum in the binary search using iteration.

  6. (1 pt) A binary search tree has n nodes. Determine the worst-case runtime complexity using Big-O notation for the following operations on the binary search tree if the tree is balanced and if the tree is not-balanced. A binary tree is balanced if every level is full except possibly the last level.


    Operation    		 Balanced BST Non-balanced BST
    Traverse    
    Find    
    Add    
    Remove    

  7. (1.5 pts) Rewrite the find method for the BinarySearchTree class discussed in lecture so that it is iterative, not recursive.

  8. (2 pts) Use the remove algorithm discussed in class to remove a node from the binary search tree shown below. Draw the resulting tree based on the algorithm (and the associated code given in lecture). For each answer, show the sequence of recursive calls made and the reference returned for each recursive call.

    1. Remove node 65 from the original tree.

    2. Remove node 16 from the original tree.

    3. Remove node 12 from the original tree.

    4. Remove node 42 from the original tree.

PROGRAMMING PROJECT (10 points)

A popular puzzle requires the player to fill in a 9 X 9 grid with the numbers from 1 to 81. The catch is that the numbers must form a path from 1 to 81, connecting horizontally and vertically only (not diagonally). The figures below show an initial puzzle and then the solution showing the path that connects the numbers in order from 1 to 81.

The puzzle begins with the numbers shown in the shaded spaces above. The player has to fill in the remaining numbers.

Assignment

Write a Java class NumberPuzzle that reads in the initial state of the puzzle and then outputs the unique solution to the puzzle. Your solution should use recursion and backtracking.

The size of the puzzle will be N × N, using the numbers 1 to N2, where 6 ≤ N ≤ 10. The initial numbers provided can be in any position of the board (not just the shaded area shown in the example). You may NOT assume that the value 1 is given to you initially.

Input Format

You will read the input puzzles from a text file with the following format. The first line of input will be the number of test cases to be executed, followed by the data for each test case. For each test case, the first line will indicate the dimension of the puzzle as a single integer (between 6 and 10 inclusive). The following N lines will contain N integers per line separated by whitespace, representing the initial puzzle. Blank cells are represented by the value 0; non-blank cells are represented by their individual values. You may assume that the number of values per line and number of lines per puzzle is correct based on the given dimension of the puzzle.

Here is an example of an input data file with 2 puzzles, the first puzzle matching the example shown in the picture above. 

2
9
0 0 0 0 0 0 0 0 0
0 81 76 75 72 65 62 61 0
0 6 0 0 0 0 0 56 0
0 1 0 0 0 0 0 55 0
0 10 0 0 0 0 0 50 0
0 13 0 0 0 0 0 51 0
0 20 0 0 0 0 0 44 0
0 19 22 27 26 35 38 39 0
0 0 0 0 0 0 0 0 0
6
0 0 12 13 0 0
9 0 0 0 0 16
0 0 4 5 0 0
0 0 23 22 0 0
0 1 0 0 26 0
0 0 31 30 0 0

Output Format

For each test case, your output should consist of N lines showing the final solution to each puzzle, row by row, where N is the dimension of the puzzle. Each line should have N numbers separated by a single space between each number. Print one blank line between test cases for readability.

Here is the sample output 

79 78 77 74 73 64 63 60 59 
80 81 76 75 72 65 62 61 58 
7 6 5 4 71 66 67 56 57 
8 1 2 3 70 69 68 55 54 
9 10 11 30 31 48 49 50 53 
14 13 12 29 32 47 46 51 52 
15 20 21 28 33 34 45 44 43 
16 19 22 27 26 35 38 39 42 
17 18 23 24 25 36 37 40 41 

10 11 12 13 14 15
9 8 7 6 17 16
36 3 4 5 18 19
35 2 23 22 21 20
34 1 24 25 26 27
33 32 31 30 29 28

Programming Guidance

First, solve this problem assuming that the number 1 is given in the initial puzzle. Once you have this working, save a copy of this program elsewhere, then determine what you need to change to make the program work if the number 1 is not present. If you can't get this version of the program to work correctly, you can hand in the previous version to maximize your partial credit.

Documentation & Style

Be sure to document all of the code that you write to explain what you are doing. Use appropriate Java style (indentation, variable names, etc.) to make your code as readable as possible.

Hand-In Instructions & Late Submissions

Your submitted zip file should include the complete Java program.

See the course website for instructions on how to hand in your program and the policy for late submissions.