4.37 Write a method that takes as input a binary search tree, T, and two keys k1

4.37 Write a method that takes as input a binary search tree, T, and two keys k1 and k2, which are ordered so that k1 ≤ k2, and prints all elements X in the tree such that k1 ≤ Key(X) ≤ k2. Do not assume any information about the type of keys except that they can be ordered (consistently). Your program should run in O(K + logN) average time, where K is the number of keys printed. Bound the running time of your algorithm.
4.46, Two binary trees are similar if they are both empty or both nonempty and have similar left and right subtrees. Write a method to decide whether two binary trees are similar. What is the running time of your method.
** 4.37. Note: For problem 4.37 please ignore the last sentence that starts with “Bound the running time…”.
Deliverables:
1. Method code in .java files. Only submit the code of the method that 4.37 and 4.46 are asking for. Do not include your BST implementation.
2. Driver.java with the main method that includes the test code you wrote to your methods.
3. Screenshots showing sample outputs for all the methods you implemented in this assignment.