$1.$ Give recursive algorithms that perform preorder and postorder tree walks in $\backslash$Theta $($n$)$ time on a tree of n nodes.

$2.$ Give a recursive version of the TREE$-$INSERT procedure.

$3.$ For the set of $\{1,4,7,11,13,18,23\}$ of keys, draw binary search trees of

height $2,3,4,5,$ and $6.$

$4.$ Suppose that we have numbers between $1$ and $1000$ in a binary search tree, and we want to search for the number $400.$ Which of the following sequences could not be the sequence of nodes examined?

a$.961,257,948,281,935,295,399,400.$

b$.972,315,384,658,336,429,395,400.$

c$.39,289,438,435,367,381,434,400.$

d$.962,239,948,277,949,282,400.$

e$.39,436,424,256,303,419,418,315,400.$