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.

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

Ex6. Main (10 points)

Write a main() function that tests the functions you implemented in exercises 1-5.