NOTE: For problems Q$1-$Q$5,$ DEPTH counting starts at $1$ at the root.

$$

Q$1[15$ pts$.]$: Given the following key sequence $(5,23,8,14,13,2,7)$ build the dynamic binary search tree WITHOUT BALANCING IT$.$ How many probes $($i$.$e$.,$ comparisons$)$ does it take to determine that key $100$ is not in the tree? $($In this study case, the root is $5$; the next element $23>5,$ so it goes to the right, etc$).$

$$

$$

Q$2[5$ pts$.]$: How many leaves does a $3-$ary tree have if its depth is $7?($HINT: see the pattern for a full binary tree of depth n and modify it$).$

$$

$$

Q$3[10$ pts$.]$: How many total nodes does a $5-$ary tree have if its depth is $6?$

$$

$$

Q$4[10$ pts$.]$: Given the preorder traversal of a tree is: a$,$b$,$c$,$d$,$e and the inoder traversal of the tree is: b$,$a$,$e$,$d$,$c$.$ What is the POSTORDER traversal of that tree?

$$

$$

Q$5[15$ pts$.]$: Consider a binary tree containing n nodes.$$

$$

$($a$)$ What is the theta value for the preorder traversal of this tree?

$($b$)$ What is the theta value for the inorder traversal of this tree?

$($c$)$ What is the theta value for the postorder traversal of this tree?

Make sure there is a note above.