CSci 2101 Problem set 5.

Due Monday June 21st at 11:59pm

You may work individually or in pairs.

30 points

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 (10 points). Tree traversals.

Write methods that perform the following tree traversals: preorder traversal (Root, Left subtree, Right subtree) and reverse inrorder traversal (i.e. Right subtree, root, Left subtree). The method should use recursive helper methods in BSTNode class and should return a list (such as ArrayList) of Key-Value pairs, similar to the inorder traversal for which the test is given in class. You may use your group's implementation of BinarySearchTree or the other group's. Both will be posted.

Write tests for your methods, make sure tests pass, and submit the tests. One of the tests must include an empty tree.

Problem 3 (12 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 they have the same nodes with the same keys and values in the same positions in the tree.

More formally, two binary search trees are considered equal if for every node in one tree there is a corresponding node in the other tree (i.e. a node with the same path from the root) that has the an equal key, an equal value, has a left child if and only if the node in the original tree has a left child, and has a right child if and only if the node in the original tree has a right child.

Test your method extensively, include 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.