CSci 2101 Problem set 5.

Due Monday November 21st at 11:59pm

You may work individually or in pairs.

Problem 1 (8 points): Written part.

For this problem assume that given trees are binary (i.e. each node has at most two children, left and right), but not necessarily binary search trees, i.e. there is not relation between values of a parent and a child node. There is enough information given in each item to uniquely determine all nodes in the tree corresponding to that item.

1. Draw a picture of a tree that has the inorder traversal 5, 12, 10, 7, 8, 6, 3, 15 and the preorder traversal 7, 10, 5, 12, 3, 6, 8, 15.
2. Draw a picture of a tree that has the inorder traversal 9, 18, 2, 11, 6, 3, 7 and the postorder traversal 9, 11, 2, 18, 3, 7, 6.
3. Draw a picture of a binary search tree with the preorder traversal 10, 6, 3, 2, 8, 20, 15, 17.

Problem 2 (15 points). Tree traversals.

Write methods that perform the following tree traversals: pre-order traversal (Root, Left subtree, Right subtree), post-order traversal (Left subtree, Right subtree, Root), and and reverse in-order traversal (i.e. Right subtree, root, Left subtree). The methods should be recursive and should return a list (such as ArrayList) of Key-Value pairs, similar to the in-order traversal. I will send out the BinarySearchTree implementation that has a working put method, that should be sufficient for testing. Feel free to use tyour own, completed, version of a binary search tree.

Write JUnit tests for your methods, make sure the tests pass, and submit the tests with your code. One of the tests must be for an empty tree.

Below is the class KVPair that is used to store the node data.

/**
 * A class for storing key-value pairs generated during
 * traversals of a Binary Search Tree
 * mypair.key gives the key, mypair.value gives the value
 * 
 * @author Elena Machkasova
 *
 * @param <K> - key type (must be comparable to itself)
 * @param <V> - value type 
 */

public class KVPair<K extends Comparable<K>, V> {
	final public K key;
	final public V value;
	
	public KVPair(K key, V value) {
		this.key = key;
		this.value = value;
	}
	
	public boolean equals(Object other) {
		if (! (other instanceof KVPair)) return false;
		KVPair<K,V> otherPair = (KVPair<K,V>) other;
		return (key.equals(otherPair.key) && value.equals(otherPair.value));
	}
}

Problem 3 (10 points): binary tree equals method

Add an equals method to the BinarySearchTree class. According to Java specification, equals method takes any object. It then checks if the parameter object is of the same type as this object (see instanceof check below). If the object passes the instanceof check, it is then typecast to BinarySearchTree<K,V>. See more on instanceof here: http://www.java2s.com/Tutorial/Java/0060__Operators/TheinstanceofKeyword.htm.

The method is declared and starts as follows:

public boolean equals(Object obj) {
     //  checking that obj is an OurLinkedList
     if (!(obj instanceof  BinarySearchTree) ) return false;
     
     // typecasting obj to BinarySearchTree
     BinarySearchTree<K,V> otherTree = (BinarySearchTree<K,V>) obj;

     // the rest of your code goes here, use otherTree variable:


}

Two binary search trees are considered equal if all nodes of one tree correspond to nodes with equal keys, values, and position in the tree, and vice versa. Use equals method on values and on keys to check that they are equal.

Note that it is also the case that two trees are equal if and only if one has exactly the same in-order and post-order traversal as the other, but you are not allowed to use this property as a way to establish tree equality.

Test your method extensively using JUnit, submit all your test cases.

Submit the java file(s) with your testing code by e-mail to me. Make sure to CC your group partner (if any).

CSci 2101 course web site.