PART 2 BST AND AVL TREES In this part, you will be implementing a single class which will serve for both BST and AVL trees. Refer to avl.hpp file for the class definitions. Write your implementation in avl.cpp using the boiler code. Member functions: Write implementation for the following methods as described here. AVL (bool isAVL) Simple default constructor which initializes the isAvL flag. If the isAvL flag is set, insertions and deletions will follow AVL property. Otherwise, it will be a simple BST. void insertNode(shared_ptr> N) Inserts the given node into the tree such that the AVL (or BST) property holds. void deleteNode(Tk) Deletes the node with the given key such that the AVL (or BST) property holds. shared_ptr> searchNode(T k) Returns the pointer to the node with the given key. NULL is returned if the key doesn't exist shared_ptr> getRoot() Returns the pointer to the root node of the tree. int height(shared_ptr> P) Returns the height of the tree. Note: In Part 2 of the assignment, the height of a tree is the number of nodes in the path from the root to its deepest descendant. For example, a tree with only two nodes (a root and a child) will have height 2 and so on. As a convention, while deleting a node with 2 children, the new root should be selected from the right subtree. PART 2 BST AND AVL TREES In this part, you will be implementing a single class which will serve for both BST and AVL trees. Refer to avl.hpp file for the class definitions. Write your implementation in avl.cpp using the boiler code. Member functions: Write implementation for the following methods as described here. AVL (bool isAVL) Simple default constructor which initializes the isAvL flag. If the isAvL flag is set, insertions and deletions will follow AVL property. Otherwise, it will be a simple BST. void insertNode(shared_ptr> N) Inserts the given node into the tree such that the AVL (or BST) property holds. void deleteNode(Tk) Deletes the node with the given key such that the AVL (or BST) property holds. shared_ptr> searchNode(T k) Returns the pointer to the node with the given key. NULL is returned if the key doesn't exist shared_ptr> getRoot() Returns the pointer to the root node of the tree. int height(shared_ptr> P) Returns the height of the tree. Note: In Part 2 of the assignment, the height of a tree is the number of nodes in the path from the root to its deepest descendant. For example, a tree with only two nodes (a root and a child) will have height 2 and so on. As a convention, while deleting a node with 2 children, the new root should be selected from the right subtree