Question $6.$ Let Sn $=\{1,2,...,$ n$\}$ be the positive integers from $1$ to n$.$

$$ Describe a sequence of TreeInsert operation of keys of Sn which would cause the

resulting binary search tree to have height at least n$/2.$ Explain why the resulting tree

has height at least n$/2.$

$$ Describe a sequence of TreeInsert operation of keys of Sn which would cause the

resulting binary search tree to have height at most $2$ log n$.$ Explain why the resulting

tree has height at least $2$ log n$.$

$5$