CS 261, Spring 2013, Homework 5, Due Thursday, May 16 1. In a binary search tree formed by inserting n > 2 different values in a random permutation without rebalancing, what is the probability that the node for the median value has exactly one child node? (Hint: this event depends only on the relative order of insertion of the median value and its two closest neighbors in the sorted sequence of inputs.) 2. Give pseudocode for an algorithm range(T,l,r) that answers queries where the inputs to the query are the root node T of a binary search tree and two numbers l and r, and the output is a collection of all the keys x_i in T with l < x_i < r. Your algorithm should take time O(h+k) where h is the height of the tree and k is the length of its output. 3. Suppose that T is a splay tree, on three items with keys 1, 2, and 3, and that all three of the keys have already been searched for since the most recent time the set of keys in T changed. Based on this information, how many different shapes might T possibly have? Draw them all.