Consider inserting the following sequence of integers (in order from left to right) into an empty BST. No need to show the tree here ( may draw it in your notebook to answer the following questions)

A, 25, 8, 9, 35, 15, 22, 29, 20, B

You pick integers for characters A and B without generating any duplicates in the list.

1. Show your sequence after A and B are replaced by your choice of integers.
2. Give a pre-order, post-order and in-order traversal of the BST. [4pts]
3. What is the height of the resulting tree? [1pts]
4. pick an internal node ( no root and no leaf) and give the the depth and height of the node you picked?[2pts]
5. Evaluate the Balance factor for each node according to the definition in your textbook. [6pts]
6. Is the BST balanced? Explain. [2pts]
7. Describe the search algorithm for the node 35 in this BST. How many comparisons are done before finding node 35? [4pts]
8. Describe the algorithm for removing a node from a BST, make sure to include all cases. Pick a node with two children and describe how the node is removed. [4pts]