이진 트리, 완전 이진 트리, 이진 탐색 트리(BST)는 각각 어떤 조건으로 구분하나요?

이렇게 답해 보세요 (핵심 답변)

이진 트리는 각 노드의 자식이 최대 두 개인 트리이고, 완전 이진 트리는 마지막 층 직전까지 가득 차고 마지막 층은 왼쪽부터 차례대로 채워지는 '모양 조건'을 뜻합니다. 반면 이진 탐색 트리(BST)는 왼쪽 서브트리에는 현재 노드보다 작은 키, 오른쪽 서브트리에는 큰 키만 둔다는 '키 순서 조건'을 갖습니다. 모양 조건과 순서 조건은 별개여서 완전 이진 트리라고 자동으로 탐색 트리가 되지는 않으며, 균형이 깨진 일반 이진 트리의 높이는 최악 O(n)까지 커질 수 있습니다.

함께 설명하면 좋은 이유 (꼬리질문 대비)

1. 이진 탐색 트리에서 탐색·삽입·삭제 시간을 O(log n)으로 보장하려면 레드-블랙 트리나 AVL 트리 같은 별도의 높이 균형 조건이 필요합니다.
2. 이진 힙은 완전 이진 트리 모양을 쓰지만 부모-자식 우선순위만 맞출 뿐 이진 탐색 트리의 좌우 전체 키 순서는 따르지 않습니다.

면접에서 자주 하는 실수

마지막 층 왼쪽부터 채우는 '완전 이진 트리'와 모든 층이 빠짐없이 가득 찬 '포화 이진 트리'를 혼동하지 않아야 합니다.