Your tasks in a summary, implement the followings:

1. In-order and post-order traversals
2. The height of each node and the size of the tree
3. Searching for minimum and maximum of a tree
4. Check if an element exist in the tree
5. The successor function
6. AVL tree balancing

You can assume that a tree is not empty (size > 0) for Tasks 3 and 5. Therefore, you code should work for the rest even if the tree has no node. First, please aim at finishing Tasks 1 to 4. Tasks 5 and 6 could be considered as more difficult.

Over all, you are allowed to (and you should) add more member variables and functions to the two given classes. However, remember to copy and paste the code for the class definitions also.

In order to avoid lengthy wording, BST stands for Binary Search Tree in this worksheet.

Skeleton Code

You are given three files with some basic implementations of a binary search tree:

• cpp, BST.h, BST.hpp

The following functionalities are already implemented for you:

• Basic insertion without balancing
• Print out all the nodes according to pre-order traversal
• Print out the tree structure with a 90 degree anti-clockwise rotation

Task 1 In-order and Post-order Traversals

The pre-order traversal is implemented for you. Your job is to implement the in-order and post order traversal.

Sample output:

Task 2 Size of the Tree and Height of Node

The size of the tree is the number of the elements being inserted into the tree. Currently, the _size member is zero and not set correctly. So does the height of each node (_height). Here is the correct sample input if you implemented them correctly.

Task 3 Search Min/Max

Uncomment testSearchMinMax() in main(). Implement the functions searchMin() and searchMax() in BST. Here is the sample output for the tree in the code:

Task 4 Search for an Element in the Tree

Uncomment testExist() in main(). Similar to the Linked List assignment, implement a function exist(x) to return true if x is in the tree, and false otherwise.

Task 5 Successor

Uncomment testSuccessor() in main(). Implement the function successor(x) in BST such that it will return the successor of x:

Task 6 AVL Tree Balancing

If you have reached this point, congratulation! However, here is the final boss you have to fight. Your tree should work fine so far for the above functionalities. At this point, we highly recommend you to save and backup all your work so far. Zip them up and copy them to a safe location.

Uncomment testInsertion2 () in main()and you will get a skewed tree like this. This is because the balancing has not been implemented yet.

In order to balance the tree, you should

• Implement the left and right rotations (refer to the notes and Lab 4 slides)
• Add additional code in the insertion function to balance the tree after insertion.

If you have implemented correctly, your tree in the Insertion Test 2 should be the same as the one before.

Final Result

If you have implemented everything correctly, your final output should be like this