1. Suppose we call rotateWithLeftChild on an arbitrary 2-d tree. Explain in detail all the reasons that the result is no longer a usable 2-d tree.
2. Implement the insertion and range search for the k-d tree. Do not use recursion.
3. Determine the time for partial match query for values of p corresponding to k = 3, 4, and 5.
4. For a perfectly balanced k-d tree, derive the worst-case running time of a range query that is quoted in the text (see p. 600).