Practice question · True or false
Inserting 1, 2, 3, 4, 5, 6, 7, 8 into an empty binary search tree in that order produces a tree of height 8 that behaves like a linked list.
Hints
- Each new value is larger than everything already in the tree.
- Where does a larger value always go?
Show the answer
True
Why
True. Every insertion goes right, so the tree degenerates into a right spine, search becomes O(n), the exact cost a BST exists to avoid. Sorted input is the worst case, and it is a common one. Self-balancing trees (AVL, red-black) exist precisely to rotate this back to O(log n).
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…
- A binary search tree built from sorted input degrades to a linked list, and the fix, AVL or red-black, adds…
- Select every statement the lesson supports about binary search trees.