Pete's going to post a sample solution for this one. I'll make a few comments about where I think most people lost points. I believe that the notes that I put on the assignments were probably more complete, and also better reflect what problems you had. If you have any questions about your score, or think that I dealt with you too harshly (or not harshly enough :) please come see me. Legitimate inquiries/complaints are always welcome.

Common problems:

• The biggest problem was that people tended to drop parts of the data. I think this usually occurred due to accidental mis-handling of double rotations. This and the following error probably slipped through because you failed to fully test the program. The sample data given will probably not be sufficient for testing purposes---you should make sure to supplement that data accordingly.
• The next biggest problem was that people failed to keep the tree correctly balanced, and allowed depth differences of >= 2. Make sure to check the conditions properly, and re-balance if necessary.
• Some people didn't make any apparent change to the code at all. We will notice this.
• Comment your code! Many people included 0 comments of the code that they added. This code is not trivial, and requires some explanation of what you've done.
  (As a practical matter, even if you don't think that you need the comments in there, if you do get your code wrong, you're much more likely to receive partial credit if we can sort out what you've tried to do.)
• This isn't a programming error, but rather one of protocol: you must turn in an electronic copy via email and a paper copy.
• This isn't an error, and no points were taken off for it, but did cause me problems: some people would #include one file, say "avl.h", but turn in the file renamed to "bst.h". This made it hard to compile!

Solution by Isaac Kunen, 27.4.2000