HW 9: Binary Search Trees

- In big-O, what is the time required to build a maximum-height (stringy)
BST with N
elements?
**Carefully explain your answer.** - In big-O, what is the time required to build a minimum-height (bushy)
BST with N
elements?
**Carefully explain your answer.** - Consider the BST below:
20 / \ / \ 13 40 / \ /\ 10 18 30 50 / \ \ 15 19 35 / \ / \ 14 17 32 38 \ 39

Show the tree you get after removing the values below in the order given. Remove each value from the tree as modified so far; e.g., remove 38 from the tree that already has 10 removed, not from the original tree.10 38 13 40 20

Be sure to use the removal algorithm discussed in the text -- don't just eyeball it. (The text actually has a limited discussion of how to remove an element, although it does include complete code. You might also want to look at one of the many discussion of this topic online.) - Could the largest value in a BST be at a leaf? Could it have one child?
Could it have two children? Explain your answers.
- Could the largest value in a BST be at the root? Explain your answer.