Quando precisamos procurar um elemento de um dado valor v em tal árvore, fazemos isso recursivamente da seguinte maneira. Se a árvore estiver vazia, a pesquisa termina em fracasso. Se a árvore não estiver vazia, comparamos v com a raiz da árvore K(r). Se eles corresponderem, um elemento desejado será encontrado e a pesquisa poderá ser interrompida; se eles não corresponderem, continuaremos com a pesquisa na subárvore esquerda da raiz se v < K(r) e na subárvore direita se v > K(r). Assim, em cada iteração do algoritmo, o problema de pesquisar 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 é a sua altura; obviamente, a diminuição na altura de uma árvore normalmente muda de uma iteração para outra da árvore binária, dando-nos assim um excelente exemplo de um algoritmo de redução de tamanho variável.