Counting Tree Operations
CIS 323
Winter 2007
Assignment 2

Making and working with Binary Search Trees

Due 5pm Tuesday 6 February 2007

In this assignment you are going to end up implementing a recursive data structure (Binary Search Trees) and do a non-recursive version of an algorithm that is usually done recursively (Depth First Search/Euler Tour)¹. Pretty neat! Recursion where you're not used to it and iteration where you are.

Let us define tree operations to be "insert a data element" and "snip off a node and its subtree". Given two binary search trees, T₁ and T₂, how many tree operations does it take to transform T₁ into T₂?

Input Specification

The trees will be specified as a number of nodes, followed by that many numbers (all of them unique and in the range -2³¹ and 2³¹-1). To generate the trees from this sequence insert them in order into a BST. After you have read in two trees, calculate and print how many operations it would take to transform the first tree into the second. Then, you may or may not be required to read in two more tress and do it all again. End of input is indicated by the signal value of -1 nodes in the tree. Some sample input should help clear up any questions:

Input:

4 1 2 3 4  5 1 2 3 4 5
4 1 2 3 4  4 1 2 3 5
2 0 1  1 9
1 9  2 0 1
5 4 89 34 129 32222  0
0  0
0  1 1
2 34 3987  2 34 3987
2 34 3987  2 35 3987
2 34 3987  2 34 3988
-1

Output:

1
2
2
3
1
0
1
0
3
2

Which is the number of changes required for each of the pairs of trees listed above. Each pair of trees will be on its own line, but you should not depend on whitespace beyond that when you are reading in the data - I reserve the right to put random tabs and spaces in the input. Don't worry - StringTokenizer, split(), cin, and scanf should all still work as advertized, just don't depend on how much whitespace separates 2 numbers.

A giant test case is included in the file huge.in

Implementation Strategy

Depth first search the two trees in parallel. Don't use built-in data structures for the BST, you have to write your own.

1. Note that there is a recursive solution to this problem, and if that one is more natural for you, then you are welcome to go with that one. The iterative one seemed obvious to me, and the recursive one was more obscure, but you may implement either one and you will get full credit either way.
2. This, like many other problems, is not an original problem. It is derived from a problem on an ACM competition a few years back. When I note this fact, it ceases to be plagiarism, and is instead citation.

Grade Curve

Grade Bucket	Count
0
10
20
30
40
50
60
70
80
90
100

Questions?