The worst-case time complexity for deleting a key from a Binary Search Tree (BST) is O(N), with this scenario arising when the BST is unbalanced and resembles a linked list. While the average complexity might be O(log N) for a balanced tree, the worst-case must consider the linear time complexity due to the tree's potential skewed shape.
The worst-case time complexity of deleting a key in a Binary Search Tree (BST) containing N keys is O(N). This worst-case scenario occurs when the BST is skewed, resembling a linked list rather than a balanced tree. In a well-balanced BST, the average time complexity for deletion would be closer to O(log N), but since the question asks for the worst-case, we must consider the unbalanced scenario.
In the process of deletion, the algorithm may need to find the minimum or maximum in a subtree (if the node to be deleted has two children), which takes O(h) time, where h is the height of the tree. In a balanced BST, this would be O(log N), but in a skewed tree, this becomes O(N). Thus, the worst-case complexity for deletion in a BST is linear with respect to the number of nodes.
The worst-case time complexity for deletion in a vanilla Binary Search Tree is O(N), due to the potential unbalanced nature of the tree.