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 pesquisa 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 sensata 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, assim, um excelente exemplo de um algoritmo de diminuição de tamanho variável.