Not only finding the element,we might have to search for inorder predecessor or successor incase if the deleted node has 2 children ... In worst case for finding inorder predecessor or successor we might take O(n) time as we might in worst case travel height of tree approximately .. Anyway overall O(n) time only for deletion ..