Obviously, the brute force method of:
DeleteRange(root, low, high) for n = low to high if n == root.key // key found return DeleteNode(root) // O(lg n) to delete elseif n < root.key // in left sub-tree root.left = DeleteRange(root.left, n, high) // recur into left sub-tree elseif n > root.key // in right sub-tree root.right = DeleteRange(root.right, n, high) // recur into right sub-tree else // root.key == null, key not found return null return root
would take $O(n\lg n)$ time. So is there any "smarter" way of deletion that would do the same thing with less complexity, perhaps pruning entire sub-trees at once? Assume that the deleted nodes are not needed and the only concern is with returning the root of a binary search tree where the nodes between the range of two keys are deleted.