What are the worst-case complexities of insertion and deletion of a key in a…

Answer: θ(n) for both insertion and deletion (worst-case).

• Why insertion is θ(n) in the worst case:

  To insert a key you compare and descend from the root to an appropriate leaf. The time is proportional to the tree height. In a skewed tree the height is n, so insertion takes θ(n).

• Why deletion is θ(n) in the worst case:

  Deletion requires locating the node (O(height)) and then removing or replacing it. If the node has two children, you typically find its successor or predecessor (which can require another descent). All these steps are bounded by the tree height, which can be n in a skewed tree, so deletion is θ(n).

• Note about balanced trees and average case:

  If the tree is height-balanced (for example AVL or Red-Black trees) or if keys are inserted in random order on average, the height is Θ(log n) and both operations become Θ(log n). The question asks for worst-case complexity for a plain binary search tree, so the correct worst-case answer is Θ(n).