Quando precisamos pesquisar um elemento de um determinado valor v em tal árvore, fazemos isso recursivamente da seguinte maneira. Se a árvore estiver vazia, a busca termina em fracasso. Se a árvore não estiver vazia, comparamos v com a raiz da árvore K (r). Se corresponderem, um elemento desejado é encontrado e a pesquisa pode ser interrompida; se não coincidirem, continuamos com a busca na subárvore esquerda da raiz se v <K (r) e na subárvore direita se v> K (r). Assim, a cada iteração do algoritmo, o problema de pesquisa em uma árvore de pesquisa binária é reduzido a pesquisar em uma árvore de pesquisa binária menor.
A medida mais sensível do tamanho de uma árvore de busca é sua altura; obviamente, a diminuição na altura de uma árvore normalmente muda de uma iteração para outra da pesquisa da árvore binária, dando-nos um excelente exemplo de um algoritmo de diminuição de tamanho variável.
No pior caso da pesquisa por árvore binária, a árvore é severamente distorcida. Isso acontece, em particular, se uma árvore é construída por inserções sucessivas de uma sequência crescente ou decrescente de chaves
Obviamente, a busca por an − 1 em tal árvore requer n comparações, fazendo com que a eficiência do pior caso da operação de busca caia em 
. Felizmente, a eficiência do caso médio acaba sendo em