## CSci 2101 Data Structures: Problem set 4

Due Friday, November 12th at 8pm.

### Problem 1 (paper and pencil): reconstructing a tree given two traversals (18 points total)

For this problem assume that you are working with a binary trees of integers (not necessarily binary search trees, i.e. the nodes of a tree don't have to be ordered in any way). Assume that trees can't have duplicated elements.

#### Part 1 (1 point)

It is possible to have two different trees which will have the exact same result of an in-order traversal. Please draw two different trees which both have an in-order traversal ` 3 2 1 4`.

#### Part 2 (2 points)

Is it possible for two different trees that have the same pre-order traversal? Please give an example or explain why this is not possible.

#### Part 3 (10 points)

You are given an in-order and a pre-order traversals of the same tree. Using these two traversals, it is possible to reconstruct the tree itself (i.e. to figure out which node is the root and find all the left/right references of each node). Please describe (in English) the algorithm that allows you to reconstruct the tree from these two traversals. Use your algorithm on the following three test cases, draw the tree picture for each case:
In-order Pre-order
11, 3, 6, 7, 4, 10, 12 7, 11, 6, 3, 12, 10, 4
2, 10, 3, 9, 8, 5, 7, 1, 6 8, 10, 2, 3, 9, 7, 5, 6, 1
2, 9, 3, 5 5, 9, 2, 3

#### Part 4 (2 points)

Can a tree be reconstructed given its in-order and post-order traversals? Please explain your answer. You don't need to write the algorithm.

#### Part 5 (3 point)

Can a tree be reconstructed given its pre-order and post-order traversals? If your answer is YES, then sketch out the algorithm. If your answer is NO, give a counter-example: a case where a pre-order and a post-order traversals describe more than one tree.

### Problem 2: deleting a tree node (6 points)

Modify the `delete()` method of the IntBST class so that if a node has two children, it is replaced with its predecessor, not with its successor. The predecessor of a node with the data value d is the largest node in the tree with the data smaller than d. Use in-order and pre-order traversals to check your method (this way you can reconstruct the tree and check which node replaced the one you have deleted).
The code for deleting a node (replacing it with its successor if it has two children) is available here.

### Problem 3: inheritance and abstract classes (16 points)

This problem deals with a (subset) of the game of chess. this web site has all the information about chess needed for this problem (and much more!). What you need to know is that chess is played on 8-by-8 board with rows labelled from 1 to 8, and columns labelled from a to h. You also need to know how the following chess pieces move:

Your task will be to implement the behavior of these three pieces given the following abstract class:

``````
abstract class ChessPiece {
protected String name;
protected char color; // black or white piece
protected int row;
protected char col;

public ChessPiece(String n, char c, char cl, int r) {
name = n;
color = c;
row = r;
col = cl;
}

public String toString() {
return color + " " + name + " at " + col + row;
}

abstract public boolean moveTo(char c, int r);

// a helper method for converting columns into numbers
// returns 1 for a, 2 for b, etc.
// returns 0 for an illegal character
protected int toNumber(char c) {
String cols = "abcdefgh";
int i = cols.indexOf(c);
if (i != -1) return i+1;
System.out.println("Illegal position " + c);
return 0;
}
}
``````
You cannot modify the abstract class.

You need to write the classes King, Rook, and Pawn. Each of these classes extends the ChessPiece class. The abstract class provides a constructor and a toString() method. It also provides a protected toNumber() method which converts a character (a column name, such as a or d) to a number from 1 to 8.

The abstract class requires that every class that inherits from it has a moveTo() method. The method takes the new position of the piece. It checks whether the move is legal (based on the specific rules of how this piece moves and on the current position). If the move is legal, then the piece is moved and the method returns 'true', otherwise the method returns 'false' and the position is unchanged.

Below is the sample of a test program for a King:

``````
King whiteking = new King('W','e',4);
King blackking = new King('B','a',8);
if (!whiteking.moveTo('d',4)) {
System.out.println("can't move the king to d4");
}
System.out.println(whiteking);
if (!blackking.moveTo('b',7)) {
System.out.println("can't move the king to b7");
}
System.out.println(blackking);
if (!blackking.moveTo('b',7)) {
System.out.println("can't move the king to b7");
}
if (!blackking.moveTo('b',5)) {
System.out.println("can't move the king to b5");
}
``````
The white king is initially at e4, the black one is at a8. The first two moves are legal, so the white king gets moved to d4, and the black king to b7. The next move is illegal because the king remains at the same position (an error message gets printed). The last move is illegal because b5 is not next to d4, and another error message gets printed.

For this problem you need to:

• Implement the three classes. Note that the behavior of a pawn depends on the color, since it can't move backwards. You may ignore: castling for the king, promotion to a queen for a pawn, blocking of one piece by another of the same color (even if a piece is blocked, the move should still be considered legal).
• Write a program to test the behavior (in particular, make sure that the program disallows illegal moves).
• Write another test program in which you create an array of ChessPieces that represents this configuration. Print out the positions of all pieces (in a loop, using the toString() method of ChessPiece). Allow for possible null values in the array (your printing loop should skip over null values without printing them and without breaking).
• Implement the solution of this chess problem (follow the link). When a piece is taken, set the corresponding element of the array to null. Print out all the positions after each move. Ignore the promotion of the pawn to a queen in the third move (just keep it as a pawn).

This is a problem set from CSci 2101 course.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.