Considere a árvore com n = 3 níveis e 2³-1 = 7 nós:
.......... ( 10 ) nível 1
........../ \
.......( 6 )....( 15 ) nível 2
....../ \.........../ \
( 1 ) ( 8 ) ( 13 ) ( 20 ) nível 3
Um nó é pai de duas folhas quando está no nível 2 (ou seja n-1), pois as folhas são aquelas que não contém filhos.
Caso o nó 6 seja removido e reinserido, ele perderá seus filhos e virará um nó folha.
.......... ( 10 ) nível 1
........../ \
.......( 6 )......( 15 ) nível 2
....................../ \
................ ( 13 ) ( 20 ) nível 3
Suponha que quero saber se 15 foi o nó que perdeu seus filhos. Para isso, comparo primeiro a raiz e vou descendo: para a esquerda se for menor ou igual e para a direita se for maior.
.......... ( 10 ) 10 <= 15 +1 comparação
........../ \
.......( 6 )......( 15 ) 10 <= 15 +1 comparação
....................../ \
................ ( 13 ) ( 20 )
Porém, não é só porque achei o 15 que ele foi removido e reinserido. É preciso adicionalmente checar se o 15 é um nó nulo, ou seja, se seus dois filhos são inexistentes. Isso significa adicionar 2 ao total de comparações. Ou seja, no total são 4 (n+1): as duas primeiras para chegar ao nó e mais duas para checar seus filhos.