**🔗 참고 문제** → [<https://www.acmicpc.net/problem/1991>](<https://www.acmicpc.net/problem/1991>)      // 클릭 시 이동

• 완전 이진 트리가 아닌, 이진 트리일 경우
  • 완전 이진 트리는 n개의 노드가 주어지면, arr[n + 1] 같은 형식으로 사용 가능
  • 일반 이진 트리는 각 노드가 어느 index에 할당될지 확신할 수 없으므로, 최대 arr[2ⁿ] 만큼의 크기 할당 필요
    • 편향 트리에서는 h = n 이 될 수 있음
  • 이는 매우 큰 수치이므로, 일반 이진 트리는 배열로 트리를 구성하기 어렵고, 문제에 부적합한 경우가 많음

🚮 선입견을 버리자

• arr[2 * i] , arr[2 * i + 1] 을 참조하는 방식은 보통 완전이진트리 / 레벨순 배열 입력에 적합
  • 완전 이진트리는 위와 같은 힙 방식으로 풀이하는 것이 정석
• 편향 트리처럼 트리가 한 쪽으로 치우치면 인덱스가 빠르게 커짐
  • 우측으로만 내려가면 인덱스가 1 → 3 → 7 → 15 → …
  • 높이 n 에서 인덱스가 2ⁿ 까지 커질 가능성 존재
• 실제 노드는 N개일 뿐인데, 배열 인덱스는 지수적으로 증가
  • 메모리 낭비가 심하고 OOM 원인
• 이진 트리를 구성하는 문제에서는 left[] 와 right[] 배열을 사용하자.

💭 어떻게 떠올릴까

1. 입력이 부모-자식 관계로 주어짐
   • 연결관계 저장 필요
   • left[node] , right[node] 방식을 떠올리자
2. 노드 번호/라벨이 작고 직접 인덱싱 가능
   • A~Z , 1~N 이면 배열을 우선적으로 사용하자
     • left[26] , right[26] → 26가지 알파벳을 담을 왼쪽, 오른쪽 노드 배열
     • left[N + 1], right[N + 1] → 인덱스 기준으로 적재

✏️ 순회를 재귀 DFS 처리 시, 시간복잡도는 O(N)