Question 2 (a) The following is the pseudocode for a recursive algorithm to print the values stored in a Binary Tree (in no particular order):

1 p r i n t T r e e ( B T N o d e t )

2 f 3 i f ( t ! = END )

4 f

5 p r i n t ( t . v a l )

6 p r i n t T r e e ( t . l e f t )

7 p r i n t T r e e ( t . r i g h t )

8 g

9 g

Give the pseudocode of a non-recursive algorithm to print the contents of a Binary Tree (in no particular order) with a complexity that is no worse than the above recursive algorithm. Hint: you may use a Stack Abstract Data Type in your answer. [10 marks] (b) Consider an AVL-Tree of positive integers that does not allow duplicate values in the tree. The insertion of the value 10 into a minimal such AVL-tree that is of height 3 triggers a double rotation. Draw the diagram of this tree both before the insertion and after the insertion has concluded.