If your first name starts with a letter from A-J inclusively:

Our implementation of the treeSearch utility, from Code Fragment 11.3, relies on recursion. For a large unbalanced tree, it is possible that Java’s call stack will reach its limit due to the recursive depth. Give an alternative implementation of that method that does not rely on the use of recursion.

Hint Use a loop to express the repetition.

Write a Java/Python application to test your solution with tree of fig 11.1 from textbook .

If your first name starts with a letter from K-Z inclusively:

Our implementation of the treeSearch utility, from Code Fragment 11.3, relies on recursion. For a large unbalanced tree, it is possible that Java’s call stack will reach its limit due to the recursive depth. Give an alternative implementation of that method that does not rely on the use of recursion.

Hint Use a loop to express the repetition.

Write a Java/Python application to test your solution with tree of fig 11.7 from textbook .

(5 marks)

Implement a bottom-up merge-sort for a collection of items by placing each item in its own queue, and then repeatedly merging pairs of queues until all items are sorted in ascending order within a single queue. Hint: A queue of queues can be very helpful.

Write a Java/Python application to test your solution.

(5 marks)