Considere o algoritmo a seguir, escrito em pseudocódigo, para inserir um novo valor z em uma árvore de busca binária A com n nós e altura h. 

1             y = NULL 2             x = A.raiz 3             ENQUANTO x ≠ NULL FAÇA: 4              y = x 5             SE z.chave < x.chave: x = x.esquerda 6             SE NÃO: x = x.direita 7             z.p = y 8            SE y = NULL: A.raiz = z 9            SE NÃO: 10               SE z.chave < y.chave: y.esquerda = z 11          SE NÃO: y.direita = z

O algoritmo acima é executado no tempo