You are given an undirected tree T = (V, E). In this problem we will find the diameter of the tree in 3 different ways.

a. Write the following:

1. A recursive algorithm to find the *diameter of the graph, based on the leaf pruning method discussed in lecture.

2. An iterative algorithm to find the *diameter of the graph, based on the recursive version you came up with and the leaf pruning method. Compute the complexity of this version. There exists a O(|E|) iterative implementation of the recursion.

b. Show how you can find the *diameter of the graph in O(|E|) time by running BFS twice.

c. Find the diameter of the graph by **rooting the tree, and a recursive call from the root asking for the diameter of each subtree hanging from each of its child.