Project ForgeData Structures
Trees
GATE 2015
Easy
What are the worst-case complexities of insertion and deletion of a key in a (plain, unbalanced) binary search tree?
- AΘ(log n) for both insertion and deletion
- Θ(n) for both insertion and deletion
- CΘ(n) for insertion and Θ(log n) for deletion
- DΘ(log n) for insertion and Θ(n) for deletion
Explanation
A plain BST has no balance guarantee — in the worst case (a fully degenerate, linked-list-like tree of height n), both a search-to-insert and a search-to-delete must walk the entire height, giving Θ(n) for both operations in the worst case.
Source: GATE CS 2015 (Session 1 / 7th Feb Shift 1) (2015)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.