이진 탐색 트리에서 키값이 x인 원소를 탐색하는 경우를 생각해 보자. 탐색은 항상 루트 노드에서 시작하므로 먼저 키값 x와 루트 노드의 키값을 비교한다. 비교한 결과는 다음 세 가지 경우 중 하나가 된다.

• ( 키값 x = 루트 노드의 키값 ) 인 경우 : 원하는 원소를 찾았으므로 탐색 연산 성공
• ( 키값 x < 루트 노드의 키값 ) 인 경우 : 루트 노드의 왼쪽 서브 트리에서 탐색 연산 수행
• ( 키값 x > 루트 노드의 키값 ) 인 경우 : 루트 노드의 오른쪽 서브 트리에서 탐색 연산 수행

이진 탐색 트리에서 루트 노드의 왼쪽 서브 트리와 오른쪽 서브 트리 역시 이진 탐색 트리이므로 서브트리에 대해서도 탐색 연산을 순환적으로 반복한다. [ 알고리즘 7-4 ]는 이진 탐색 트리의 탐색 연산에 대한 알고리즘이다.

[ 알고리즘 7-4 ] 에 따라 다음 이진 탐색 트리에서 원소 11을 탐색해 보자.

① ( 찾는 키값 11 > 루트 노드의 키값 8 ) 이므로 오른쪽 서브 트리를 탐색한다.

② ( 찾는 키값 11 > 노드의 키값 10 ) 이므로 다시 오른쪽 서브트리를 탐색한다.

③ ( 찾는 키값 11 < 노드의 키값 14 ) 이므로 왼쪽 서브 트리를 탐색한다.

④ ( 찾는 키값 11 = 노드의 키값 11 ) 이므로 탐색 성공으로 연산이 종료된다.