Language: C++

Ex1. DLL2BST (15 points) Add a constructor that constructs the binary search tree from the given DLList. BST:: BST (const DLL& list) Ex2. Find the Second Minimum (25 points) Write a member function called int BST::Find_Second_Minimum() const. The function retrieves the value of the node that has the second minimum value in the current BST. The second minimum is the element just greater than the minimum number. The running time of your implementation should be o(h). Ex3. Get the Longest Path (25 points) Write a member function called DLList BST:: get_longest_path() that returns a DLL of the longest path in the tree. For example, the red nodes in the following tree are on the longest path and should be added to the list. In case there are multiple longest paths, retrieve any of them. Ex4. Extract SubTree (25 points) Write a BST member function BST BST:: Copy_subTree (const T& n) that will extract and return the subtree rooted at the node containing the value n. For example, on the following tree, the function should return the subtree shown to the right. The current tree The returned BST The current Tree after calling the function 12 12 7 30 2 30 9 14 39 14 39 Ex5. New Traverse (Bonus 20 points) Write a BST member function void BST::BFT() that will print the tree elements in the way that is shown in the next figure 100 (200 10 30 150 (300 Ex6. Main (10 points) Write a main() function that tests the functions you implemented in exercises 1-5. 1 #pragma once 2 template class BST; 3 template 4 class BSTNode{ 5 private: I val; 7 BSTNode* left; BSTNode* right; 9 int depth; 10 int height; 11 friend class BST; 12 public: 13 BSTNode(const T& V, BSTNodex left, BSTNode* right); 14 ~BSTNode() {}; 15 I get_val() { return val;} 16 BSTNode* getLeft() { return left; } 17 BSTNode* getRight() { return right; } Lo 60 000 8 18 }; 19 20 template 21 BSTNode:: BSTNode (const T& V, BSTNode* left, BSTNode* right) { 22 val = V; 23 this->left: left; 24 this->right=right; 25 depth = height= -1; // Not computed yet 26 } 1 #include "BST.h" 2 #include 3 using namespace std; 4 5 // Implement the functions required in exercises 1-5 here // 6 7 0 8 9 // Provide your solution for exercise 6 here // 10 11 int main() { 12 13 cout