> For the complete documentation index, see [llms.txt](https://cs61b-2.gitbook.io/cs61b-textbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs61b-2.gitbook.io/cs61b-textbook/16.-adts-and-bsts/16.7-exercises.md). # 16.7 Exercises ## Factual 1. What is the best and worst-case height of a BST?
Problem 1 If we insert everything in order, the worst-case height of $$\Theta(N)$$ results. In the best case of a perfectly balanced BST, the best-case height is $$\Theta(\log N)$$.
## Procedural 1. 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? * [ ] 10, 9, 8, 7, 6, 5 * [ ] 4, 10, 8, 7, 5, 3 * [ ] 1, 10, 2, 9, 3, 8, 4, 7, 6, 5 * [ ] 1, 2, 6, 8, 9, 5 2. Consider the below BST. What is the result after deleting 4 using Hibbard deletion, choosing the sucessor as the replacement?
3. Suppose we implement the Stack ADT using an array. What is the worst case runtime of a `push` operation with this underlying data structure?
Problem 1 * [x] `10, 9, 8, 7, 6, 5`: possible; this is the situation where we have a worst-case linear BST. * [ ] `4, 10, 8, 7, 5, 3`: not possible; we terminate our search once we reach the desired node. * [x] `1, 10, 2, 9, 3, 8, 4, 7, 6, 5`: possible; the idea is that we should always search in the correct "direction" of our target node. If our target node is greater than our current node, then we should go to the right, and our next node should be larger. If our target node is less than our current node, then we should go to the left, and our next node should be smaller. * [ ] `1, 2, 6, 8, 9, 5`: not possible; note that this violates the constraint described above. When we reach `8`, we should move to its left branch since our target node `5` is smaller, so we would never search `9`.
Problem 2 ![](/files/LsjdpZl8rkzaVOdA9zRr)
Problem 3 The worst-case runtime is $$\Theta(N)$$, since a `push` might cause us to resize the underlying array.
## Metacognitive 1. 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? 2. 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?
Problem 1 Often in real-world applications, we don't have all our data at once. For example, imagine you're collecting time-based data that you insert into a BST each time a new value is reported. There is no easy way to shuffle your data when you only get one or a few points at a time.
Problem 2 By definition, the successor is the maximum value in the subtree. Suppose, for the sake of contradiction, that the sucessor had two children. Then, it is not the maximum, since it is less than its right child. This is a contradiction, since we said the sucessor is the maximum value in the subtree. As such, the successor is guaranteed to have one child or less (if it has one child, it is its left child). Previous 16.6 Summary Next 17. Tree Traversals and Graphs
--- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter: ``` GET https://cs61b-2.gitbook.io/cs61b-textbook/16.-adts-and-bsts/16.7-exercises.md?ask=&goal= ``` `ask` is the immediate question: it should be specific, self-contained, and written in natural language. `goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.