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 rootwould 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.
Delete a range of keys in a binary search tree in better than $O(n\lg n)$?
algorithms;binary trees;search trees