Show that any n-node binary tree can be converted to any

Question

Problem

1. Show that any n-node binary tree can be converted to any other n-node binary tree using O(n) rotations.

2. Let D be an ordered dictionary with n entries implemented by means of an AVL tree. Show how to implement the following operation on D in time O(logn + s), where s is the size of the iterator returned:

Find All I n Range(k₁,k₂): Return an iterator of all the entries in D with key k such that k₁ ≤ k ≤ k₂.