Quando se precisa buscar um elemento de um determinado valor v em tal árvore, faz-se isso recursivamente da seguinte maneira. Se a árvore estiver vazia, a busca termina em fracasso. Se a árvore não estiver vazia, compara-se v com a raiz da árvore K(r). Se eles corresponderem, um elemento desejado será encontrado e a busca pode ser interrompida; se não coincidirem, a busca continua 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 busca 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.