Consider the following undirected binary tree T with 17 vertices.

1. Let T be an undirected binary tree with n vertices. Write an efficient algorithm that shows how you can walk through the tree by crossing each edge of T exactly twice: once in each direction.

Clearly explain how your algorithm works, why each edge is guaranteed to be crossed exactly twice, and determine the running time of your algorithm.

2. Let T be an undirected binary tree with n vertices. Create an algorithm to compute the diameter of T. Clearly explain how your algorithm works, why it guarantees the correct output, and determine the running time of your algorithm.