A$.1.$List the nodes visited with a preorder traversal.

$2.$List the nodes visited with an inorder traversal.

$3.$List the nodes visited with a postorder traversal.

$4.$ How many internal nodes are there?

$5.$How many leaves are there?

$6.$What is the maximum width of the tree?

$7.$What is the height of the tree?

$8.$What is the diameter of the tree?

$9.$Is the tree a binary search tree tree? YES$/$NO If not, which node or nodes violate the BST property?

B$.$ Draw the final binary search tree that results after inserting the following keys in the order they appear here: $67,18,45,76,41,12,82,79,70,14,42,44$

C$.$ Solve the recurrence relation below. Show $2$ backwards substitutions, $1$ general form of the recurrence, use of the initial condition, and the final answer. Use variable $i$ in steps $c$ and $d.(10$ points$)x(n)=2x(n-1)$ for all $n>1,x(1)=5$