1. Design a recursive linear-time algorithm that tests whether a binary tree satis?es the search tree order property at every node.
2. Write a recursive function that takes a pointer to the root node of a tree T and returns a pointer to the root node of the tree that results from removing all leaves from T.
3. Write a function to generate an N-node random binary search tree with distinct keys 1 through N. What is the running time of your routine?