(a) Consider the following Binary Search tree Write down the (i) in-order traversal 2 (ii) preorder traversal (ii) postorder traversal Do you notice an interesting property of the in-order traversal? What is it? (b) Let a binary search tree be defined by the following class public class IntTree ( private IntTreeNode overallRoot; // constructors and other methods omitted for clarity private class IntTreeNode f public int data; public IntTreeNode left; public IntTreeNode right // constructors omitted for clarity In class, we saw how to search for an element in a binary search tree. This question will demonstrate that binary search trees are more powerful. Describe an algorithm that calculates the k'th smallest element in the tree. (k, the input, is a number in 1,2,.. , n], where n is the number of nodes in the tree). You may find it helpful to modify the definition of IntTreeNode in order to accomplish this. Your algorithm should run in O(h) time, where h is the height of the tree. An O(n) solution will be given partial credit