[Iterative DFS] 173. Binary Search Tree Iterator

173. Binary Search Tree Iterator

 

이 문제는 **BST(이진 탐색 트리)**의 **중위 순회(In-order Traversal)**를 반복자처럼 구현하는 문제입니다. 즉, BSTIterator 클래스는 다음 동작을 할 수 있어야 합니다:

• next()는 다음 작은 값을 반환.
• hasNext()는 더 방문할 노드가 남았는지를 반환.

💡 중위 순회(In-order Traversal)란?

BST에서 중위 순회는 왼쪽 → 루트 → 오른쪽 순서로 방문하며, 항상 오름차순 정렬된 값을 출력합니다.

---

✅ 파이썬 코드 (스택을 이용한 중위 순회 반복자)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class BSTIterator:
    # 이터레이터는 중위 순회(in-order traversal) 방식으로 노드를 하나씩 방문하게 됨
    # 중위 순회는 BST에서 오름차순으로 값을 방문하게 되는 순서임: 왼쪽 -> 자기 자신 -> 오른쪽

    def __init__(self, root: Optional[TreeNode]):
        self.stack = []

        # 초기화 시 왼쪽 자식들을 스택에 쌓아둠
        # => 가장 작은 값부터 꺼낼 수 있도록 준비
        while root:
            self.stack.append(root)  # 현재 노드를 스택에 넣고
            root = root.left         # 더 왼쪽 자식으로 이동

    def next(self) -> int:
        # 스택에서 맨 위 노드를 꺼냄 (가장 왼쪽에 있었던 노드)
        res = self.stack.pop()

        # 해당 노드의 오른쪽 서브트리가 있다면
        # 오른쪽 노드부터 시작해서 왼쪽 자식들을 스택에 추가
        cur = res.right
        while cur:
            self.stack.append(cur)  # 오른쪽 노드 및 그 왼쪽 자식들을 차례로 스택에 저장
            cur = cur.left

        # 현재 노드의 값을 반환 (중위 순회 순서대로)
        return res.val     

    def hasNext(self) -> bool:
        # 스택에 남아 있는 노드가 있다면 아직 방문하지 않은 노드가 있음
        # => next()를 호출할 수 있음
        return bool(self.stack)

 

💡 전체 흐름 요약

• __init__: 가장 왼쪽 노드까지 모두 스택에 저장 (중위 순회의 시작 준비)
• next(): 스택에서 하나 꺼내고, 그 노드의 오른쪽 서브트리가 있으면 그쪽도 중위 순회를 위해 준비
• hasNext(): 아직 순회할 노드가 남아있는지를 확인 (스택이 비었는지로 판단)

 

🌲 예시 BST

        7
       / \
      3   15
         /  \
        9    20

• 중위 순회: [3, 7, 9, 15, 20]
• next() 호출 시: 3 → 7 → 9 → 15 → 20 반환됨
• hasNext()는 그 다음이 있으면 True, 없으면 False

---

📝 요약

• 스택을 이용해 중위 순회 상태를 유지.
• next()는 스택에서 꺼내면서 오른쪽 서브트리를 탐색.
• hasNext()는 스택이 비었는지로 판단.

 

https://youtu.be/RXy5RzGF5wo