Which strings have the property that, in their suffix trees, every non-root node is a leaf? Describe the same set of strings in a different way, not involving suffix trees.
Suppose that a balanced binary search tree has been augmented so that each node stores the number of nodes in its subtree, in order to perform range counting queries. Give pseudocode for a query algorithm that uses the same information to find the median of the keys (positions) stored in the tree.
Suppose that in fractional cascading (for a collection of k ordered lists, as described in class or in the "Example" section of the Wikipedia article) we augment each list with 1/3 of the values from the following list, instead of 1/2 of the values. By what factor would this change affect the total space of the data structure, and by what factor would this affect the number of nodes examined in the search path of each query?