The keys 10, 20, 30, 40, 50 are inserted in that order into an empty, unbalanced binary search tree. What is the height of the resulting tree, counting edges on the longest path?
Correct answer D. 4
Explanation
Each new key is larger than all earlier ones, so it always becomes the right child of the previous node, producing a chain of five nodes and four edges. Such a degenerate tree behaves like a linked list, making search O(n) instead of O(log n). A height of 2 would require a balanced shape, which is exactly what self-balancing trees such as AVL trees maintain.
Answer checked How we write and check questions
Discussion