В основном вы бросаете BST, который у вас есть, и создаете новый без элемента.
Вы можете сделать это, рекурсивно спускаясь по дереву. Если ваш элемент меньше корневого элемента данных, создайте BST, корневая ветвь которого и ветвь больше, чем скопирована из имеющейся у вас сейчас, но чья ветвь меньше, чем результат рекурсивного вызова.
Это очень похоже на то, как вы добавляете узел, но когда вы добираетесь до того, который вы искали, объедините два BST под ним и верните результат. Наверняка уже существуют вопросы о том, как это сделать.