C/Visual C - Arbol Binario. Recorrido y borrado

Hola. Tengo una dudilla. ¿Alguien sabe como puedo borrar un elemento mientras realizo un recorrido en inorden recursivo? He de decir que tengo ya implementado el metod de borrar y que recorre la raiz hasta las hojas en busca del elemento en cuestion. He conseguido volcar los elementos a una cola mientras recorro, pero eso no me vale. ¿alguien me ayuda?. Gracias