Practice question · Select all that apply
Select every statement the lesson supports about binary search trees.
Hints
- One option promises something the lesson explicitly denies.
- Ask what happens to the height when the values arrive already sorted.
Show the answer
- A. Self-balancing trees exist to keep the height logarithmic
- B. An in-order traversal of a BST produces the values in sorted order
- D. Inserting already-sorted data degenerates the tree into a chain
- E. The ordering invariant lets a search discard half the remaining tree at each step
Why
The invariant, the degeneration, the sorted traversal and the purpose of self-balancing trees are all stated. The false option is the guarantee: logarithmic cost holds only when the tree is balanced, and sorted input destroys that balance, asserting the guarantee unconditionally is the exact pitfall the lesson names.
Practise Trees and Hierarchical Storage
The app has 5 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.
More questions on Trees and Hierarchical Storage
- A binary search tree has root 5. The root's left child is 3 and its right child is 8; node 3 has left child 2…
- Searching a balanced binary search tree of 1023 nodes takes at most 10 comparisons; scanning a list of the…
- Inserting 1, 2, 3, 4, 5, 6, 7, 8 into an empty binary search tree in that order produces a tree of height 8…
- A binary search tree built from sorted input degrades to a linked list, and the fix, AVL or red-black, adds…