이진 탐색 트리에 원소를 삽입하려면 이진 탐색 트리에 같은 원소가 있는지 먼저 확인해야 한다. 탐색 연산을 수행하여 성공하면 이미 같은 원소가 트리에 있다는 의미이므로 삽입 연산을 수행하지 않는다. 실패하면 삽입하려는 원소가 트리에 없다는 의미이므로 탐색 실패가 발생한 현재 위치에 원소를 삽입한다.

[ 알고리즘 7-5 ]는 이진 탐색 트리에서 삽입 연산을 하는 알고리즘이다. 이 알고리즘에서는 삽입할 자리를 찾기 위해 포인터 p를 사용하고, 삽입할 노드의 부모 노드를 저장하기 위해 포인터 q를 사용한다.

[ 알고리즘 7-5 ] 에 따라 다음 이진 탐색 트리에 원소 4를 삽입해 보자.

① ( 찾는 키값 4 < 루트 노드의 키값 8 ) 이므로 왼쪽 서브 트리를 탐색한다.

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

③ ( 찾는 키값 4 < 노드의 키값 5 ) 이므로 왼쪽 서브 트리를 탐색해야 하지만, 왼쪽 자식 노드가 없으므로 노드 5의 왼쪽 자식 노드에 탐색 실패가 발생한다.

④ 탐색 실패가 발생한 자리, 즉 노드 5의 왼쪽 자식 노드 자리에 노드 4를 삽입한다.

이진 탐색 트리에 원소를 삽입하는 과정인 [ 그림 7-35 ] 를 연결 자료구조로 표현하면 [ 그림 7-36 ] 과 같다.