BST — 정렬된 트리, 탐색/삽입

def search_bst(root, target):
    # Base case: 못 찾았거나 찾았거나
    if not root:
        return None
    
    if target == root.val:
        return root          # 찾았다!
    elif target < root.val:
        return search_bst(root.left, target)   # 왼쪽으로
    else:
        return search_bst(root.right, target)  # 오른쪽으로

# 8에서 6을 찾는 과정:
# 8 → 6<8이니 왼쪽 → 3 → 6>3이니 오른쪽 → 6 찾았다!

# 반복(iterative) 버전 — 면접에서 이걸 선호하는 경우도 있음
def search_bst_iter(root, target):
    node = root
    while node:
        if target == node.val:
            return node
        elif target < node.val:
            node = node.left
        else:
            node = node.right
    return None  # 못 찾음

def insert_bst(root, val):
    # 빈 자리를 찾으면 새 노드 생성
    if not root:
        return TreeNode(val)
    
    if val < root.val:
        root.left = insert_bst(root.left, val)
    elif val > root.val:
        root.right = insert_bst(root.right, val)
    # val == root.val 이면 중복 → 무시
    
    return root

# BST에 5를 삽입:
# 8 → 5<8 왼쪽 → 3 → 5>3 오른쪽 → 6 → 5<6 왼쪽 → 빈 자리! 삽입

# 편향 트리 예시 — 정렬된 데이터를 순서대로 삽입
# 1
#  \
#   2
#    \
#     3
#      \
#       4
#        \
#         5
# 높이 = n-1, 탐색 = O(n) ← 최악!

def isValidBST(root, lo=float('-inf'), hi=float('inf')):
    if not root:
        return True
    
    # 현재 노드가 범위 밖이면 BST 아님
    if root.val <= lo or root.val >= hi:
        return False
    
    # 왼쪽은 상한을 root.val로,
    # 오른쪽은 하한을 root.val로 좁힘
    return (isValidBST(root.left, lo, root.val) and
            isValidBST(root.right, root.val, hi))