Part 1: Expression trees ( Create a class 'ExpressionTree' that holds 'TreeNodes' (below). struct TreeNode { char element; TreeNode✶ leftChild;B TreeNode* rightChild; }; Your ExpressionTree class is a Binary Tree. It should handle the following operations: 1. When constructed with a String argument, ExpressionTree class builds an expression tree (see Lecture 13 algorithm). The root of this expression tree is held in a private member variable called 'root' of the ExpressionTree class. 2. Three separate print operations carried out using tree traversals: a. b. printInfix () - performs inorder traversal of the tree and prints the elements printPrefix () - performs preorder traversal of the tree and prints the elements c. printPostfix () – performs postorder traversal of the tree and prints the elements 3. Evaluate - if the characters of the string used to construct the tree are numbers (e.g. 1,2,3 etc.) the expression tree will evaluate the expression and print the result. Can re-use code from a2. *you do not need to provide the big 5 for Expression Tree, focus solely on constructing the tree properly using TreeNodes, and the traversal methods* Part 2: Binary Search Tree (5815) Create a class 'BST' that also holds TreeNodes, but maintains the properties of the BST the following operations: . Your BST should support find Min, findMax, isEmpty, makeEmpty, insert, remove, and the big 5 (copy constructor, copy assignment operator, move constructor, move assignment operator, and destructor). Check Lect for these method signatures. In addition, your BST must support a 'vector treeSort (vector elems)'method which takes in a vector of elements and sorts them by constructing a BST from the elements and then placing them into a sorted vector output by executing an inorder traversal over the constructed tree. Perform a timing experiment comparing the performance of treeSort to mergesort. What is the time complexity of treeSort? Report results in a comment at the top of your source code. Part 3: AVL Tree and BST construction on paperí a. Construct a BST by inserting the following elements from left to right. Show the BST after each insertion. Elems = [3,2,1,4,5,6,7,16,15,14,13,12,11,10] b. Delete the following elements from your BST [3,5,6,15,10]. Show the BST after each deletion. c. Repeat (a) but for an AVL tree. d. Repeat (b) but for an AVL tree.