The motivation behind this problem is to practice implementing binary trees and understand how stacks are used by compilers to implement recursion. You will be writing a sorting algorithm. You will first insert all the integer keys to be sorted into an initially empty binary search tree T, and then traverse T to retrieve the keys in sorted order. But instead of implementing the traversal recursively, you will use a stack. 6. You can use your stack implementation from the previous assignment but you may need to update the type stored. You are also allowed to use Java's Stack. a. Implement a binary search tree class. Each node in your implementation should have fields for a key and left and right subtrees but should not have a parent reference. The methods in the BST include b. i. Return the key at the root ii. Return the left subtree of the root ii. Return the right subtree of the root iv. Test if the tree is empty v. Construct an empty tree vi. Test if the tree contains a given value The motivation behind this problem is to practice implementing binary trees and understand how stacks are used by compilers to implement recursion. You will be writing a sorting algorithm. You will first insert all the integer keys to be sorted into an initially empty binary search tree T, and then traverse T to retrieve the keys in sorted order. But instead of implementing the traversal recursively, you will use a stack. 6. You can use your stack implementation from the previous assignment but you may need to update the type stored. You are also allowed to use Java's Stack. a. Implement a binary search tree class. Each node in your implementation should have fields for a key and left and right subtrees but should not have a parent reference. The methods in the BST include b. i. Return the key at the root ii. Return the left subtree of the root ii. Return the right subtree of the root iv. Test if the tree is empty v. Construct an empty tree vi. Test if the tree contains a given value