Lab 9: Trees (100 pts)

Due Saturday, November 21 at midnight on Catalyst

Part 1: Level Order Traversal of BST (50 pts)
    • Now that you have studied BFS, we are going to add a breath first traversal to our Binary Search Tree assignment.
    • Note that preOrderPrint, inOrderPrint and postOrderPrint are all depth first traversals of the the BST.
    • What about a breadth first traversal? 
    • We can implement a version of BFS on our BST, too!
    • Note that level order traversal is required for your course project.
    • For help writing this function, you can watch this video: BFS Level Order Traversal
    • You will also need to add the following prototypes to your BST.h file:
    //wrapper function for level order print
    void levelOrderPrint();

    //helper function for levelOrderPrint
    void printLevelOrder(Nodeptr root);

    Note: You can also use as many helper functions or classes as needed.

    • Submit your altered BST.h file, as well as your BSTTest.cpp file (where you have tested your new function) to Catalyst when you are finished.

    Part 2: AVL Rotation Practice (25 pts)
    • Show the AVL tree that results after each of the integer keys 9, 27, 50, 15, 2, 21, and 36 are inserted, in that order, into an initially empty AVL tree. Clearly show the tree that results after each insertion, and make clear any rotations that must be performed.
    • Also draw a new tree by inserting: 3, 6, 9, 13, 10, 5, 1
    • Bring these two along with your Activity 15.2 and 15.3 with you to class on Monday.

    Part 3: Prove that AVL operations are O(logn) (25 pts)
    • Prove to yourself that AVL trees result in a balanced tree where operations insert, delete and search can be performed in O(log n)
    • Write out the proof in a text document (either .txt, .pdf or .doc) and submit on Catalyst.
    • For help: You can read over the proof here.