Description
Spring 2025
Tree Traversals Write a recursive (no loops allowed) routine to determine if ALL paths from leaves to root are the same length. The tree nodes are instances of the following struct: struct Node { int key; Node *left, *right; }; However, for this application the key (or integer) in the node is not utilized and can be ignored. The function is prototyped in equal-paths.h and should be implemented in the corresponding .cpp file. // Prototype bool equalPaths(Node * root); Examples See the images below of trees with equal paths that should return true and trees that do not have all equal paths which should return false. ● You MAY define helper functions if needed in equal-paths.cpp. ● You CANNOT use a container (like a set, vector, map) to do your work. Do your work during your traversal (this is the learning goal of the problem). ● We have also provided a VERY RUDIMENTARY test program equal-paths-test.cpp that you may use and modify as desired to test certain configurations and debug your code. It will not be graded. Test your Code Run equal-paths-test.cpp for basic testing Open a new terminal: cd hw4 make equal-paths-test ./equal-paths-test Run more in-depth tests: cd hw4_tests/equalpaths-test make equalpaths_tests ./equalpaths_tests Prepare your Code for Submission Open a new terminal and cd hw4, then: Ensure you suppressed all debugging messages: grep -n “cout” equal-paths.h grep -n “cout” equal-paths.cpp Ensure you placed all includes in the proper place (for example): #ifndef RECCHECK #include #endif Make sure code compiles without warning: make equal-paths-test Ensure no Valgrind errors: valgrind –tool=memcheck –leak-check=yes ./equal-paths-test Add, commit and push equal-paths.cpp and equal-paths.h and any other files with changes (i.e git status should be clean) NextBSTs and Iterators Important Perspective: Remember that BSTs are an implementation of the set and map ADT. While a set only has keys, a map has a value associated with each key. But in any map or set, it is the key that is used to organize and lookup data in the structure and thus must be unique. In this homework you will implement a binary search trees and then extend it to build an AVL tree. We are providing for you a half-finished file bst.h (in the resources repository) which implements a simple binary search tree. We are also providing a complete print_bst.h file that allows you to visually see your tree, for help in debugging. HOWEVER to use this print function you must have a working iterator implementation. If the tree doesn’t print correctly you need to verify your iterator works and also that your insertions/removals haven’t destroyed parts of the tree. This file is already #include‘d into your bst.h and is invoked by simply calling the public print() member function on your tree (e.g. if you are in main() and have a BST object named b, then just call b.print();). You will need to complete the implementation for all seven functions that have TODO next to their declaration in bst.h. We provide additional clarifications for the following functions, where n is the number of nodes in the tree, and h is the height of the tree: 1. void insert(const std::pair& keyValuePair) : This function will insert a new node into the tree with the specified key and value. There is no guarantee the tree is balanced before or after the insertion. If key is already in the tree, you should overwrite the current value with the updated value. Runtime is O(h). 2. void remove(const Key& key) : This function will remove the node with the specified key from the tree. There is no guarantee the tree is balanced before or after the removal. If the key is not already in the tree, this function will do nothing. If the node to be removed has two children, swap with its predecessor (not its successor) in the BST removal algorithm. If the node to be removed has exactly one child, you can promote the child. You may NOT just swap key,value pairs. You must swap the actual nodes by changing pointers, but we have given you a helper function to do this in the BST class: swapNode(). Runtime of removal should be O(h). 3. void clear() : Deletes all nodes inside the tree, resetting it to the empty tree. Runtime is O(n). 4. Node* internalFind(const Key& key) : Returns a pointer to the node with the specified key. Runtime is O(h). 5. Node* getSmallestNode() : Returns a pointer to the node with the smallest key. This function is used by the iterator. Runtime is O(h). 6. bool isBalanced() const : Returns true if the BST is an AVL Tree (that is, for every node, the height of its left subtree is within 1 of the height of its right subtree). It is okay if your algorithm is not particularly efficient, as long as it is not O(n^2). This function may help you debug your AVL Tree in the next part of this problem, but it is mainly given as practice of writing recursive tree traversal algorithms. Think about how a pre- or post-order traversal can help. 7. Constructor and destructor : Your destructor will probably just call the clear function. The constructor should take constant time. 8. You will need to implement the unfinished functions of the iterator class. Note: You do NOT need to check whether the iterator is about to dereference a NULL pointer in operator*() or operator->() of the iterator. Just let it fault. It is up to the user to ensure the iterator is not equal to the end() iterator. Notes: ● Remember a BST (as well as any map implementation) should always be organized via the key of the key/value pair. ● The iterator class you write is mainly for clients to call and use to access the key,value pairs and traverse the tree. You should not use it as a helper to traverse the tree intenally. Instead use Node<k,v>* or AVLNode<k,v>* pointers directly along with internalFind, successor, predecessor etc. ● In this class we make use of static member functions. You can search online for what this means but here is a brief summary. A static member function cannot be called upon an object ( bst.static_member_func() ) and DOES NOT have a this pointer. Thus in that function you cannot try to access this->root_. Essentially, it is like a global level function shared by all instances of BSTs. It is a member of the class so if someone passes in an actual BST it CAN access private data (i.e. BST’s root_ member). We have made predecessor() a static member function and we suggest you make a static successor() function. That will be useful so that the iterator class can just call successor() when we want to increment the iterator. We use static for successor because the iterator class doesn’t have a BST pointer/reference so it couldn’t call successor if it was a normal member function. ● Very Important Warning: Please do not remove, modify, or rename any of the members (public, protected, OR private) in bst.h. You may add protected or private helper functions. protected helper functions may be useful if the AVLTree class you will code in the latter problem will also benefit from that function. If you do not heed this warning, our tests won’t work, and you’ll lose points. ● Reminder: If the tree doesn’t print correctly in your test program(s), you need to verify your iterator works (e.g. successor()) and also that your insertions/removals haven’t destroyed parts of the tree. Related Videos A video walkthrough is available and demonstrates techniques that can be used to debug either your BST or AVL tree. Test your Code Open a new terminal Run bst-test.cpp for basic testing: cd hw4 make bst-test ./bst-test Run more in-depth tests: cd hw4_tests/bst_tests make bst_tests ./bst_tests Prepare your Code for Submission Open a new terminal and cd hw4, then: Ensure you suppressed all debugging messages: grep -n “cout” bst.h Make sure code compiles without warning: make bst-test Ensure no Valgrind errors: valgrind –tool=memcheck –leak-check=yes ./bst-test Add, commit and push bst.h and any other files with changes (i.e git status should be clean) NextAVL Trees We are providing you a half-finished file avlbst.h (in the homework-resources repository) for implementing an AVL Tree. It builds on the file you completed for the previous question. Complete this file by implementing the insert() and remove() functions for AVL Trees. You are strongly encouraged to use private/protected helper functions. When you compile code that includes avlbst.h you will need to add the option –std=c++11 to the g++ compilation command. This is because of the usage of the override keyword for various virtual functions. You can read about it online but it mainly provides some additional compiler checks to ensure the signatures of a virtual function in the derived class matches the one you are attempting to “override” in the base class (i.e. if your base virtual function is a const-member but you forget to add const to the derived and thus are creating a whole new member function, the compiler will catch the error). Related Videos A video walkthrough is available and demonstrates techniques that can be used to debug either your BST or AVL tree. Test your Code Open a new terminal and cd hw4, then: Run more in-depth tests: cd hw4_tests/avl_tests make avl_tests ./avl_tests Prepare your Code for Submission Ensure you suppressed all debugging messages grep -n “cout” avlbst.h Make sure code compiles without warning make bst-test Ensure no Valgrind errors valgrind –tool=memcheck –leak-check=yes ./bst-test Add, commit and push avlbst.h and any other files that have changes (i.e git status should be clean) Next</k,v></k,v>