# 16.7 Exercises

Last updated

Last updated

Factual

What is the best and worst-case height of a BST?

Procedural

Suppose that a certain BST has keys that are integers between 1 and 10. During the search for 5, which of the following sequences of keys are possible?

Consider the below BST. What is the result after deleting 4 using Hibbard deletion, choosing the sucessor as the replacement?

Suppose we implement the Stack ADT using an array. What is the worst case runtime of a

`push`

operation with this underlying data structure?

Metacognitive

If inserting our data into a BST in random order yields $\log N$ height with high probability, why don't we just shuffle our data before inserting into the BST?

When we do Hibbard deletion from a BST, we always choose the successor as a replacement. The successor is guaranteed to only have zero or one child--why?