Question 4. Trees [ 14 marks ]

(a) Suppose we have a perfectly balanced binary search tree
(i.e. it has height K and contains N == (2K)-1 nodes).

Mark each of the following statements as True or False,
and include a short (1 sentence) statement justifying your answer.

  1. The worst case time to print the tree is roughly proportional to K.
    
    
  2. The worst case time to search the tree for a key value is roughly proportional to K.
    
    
  3. The worst case time to remove an element from the tree is roughly proportional to N.
    
    
    

(b) Suppose the structure for a tree node is defined as

struct tnode {
   int data;
   tnode *left, *right;
};
Provide a working implementation of the mirror function below:
// mirror recursively reverses the subtrees of t
//
//   e.g.   4       becomes    4
//         / \                / \
//        /   \              /   \
//       2     6            6     2
//      / \   / \          / \   / \
//     1   3 5   7        7   5 3   1
bool mirror(tnode *t)