[LeetCode] 98. Validate Binary Search Tree 풀이 (Java)

✔️ 오늘의 리트코드 공부 기록 – Validate Binary Search Tree

---

 
문제 요약 (Validate Binary Search Tree)

이진 트리가 주어졌을 때,
해당 트리가 Binary Search Tree(BST)ㅡ 인지 판별하는 문제

 

• 문제링크: https://leetcode.com/problems/validate-binary-search-tree

BST의 정의는 다음과 같다.

• 모든 노드에 대해
  • 왼쪽 서브트리의 모든 값 < 현재 노드 값
  • 오른쪽 서브트리의 모든 값 > 현재 노드 값

---

🤔 처음 떠올린 아이디어

처음에는 이렇게 생각했다.

“왼쪽 자식은 부모보다 작고,
오른쪽 자식은 부모보다 크면 되지 않을까?”

 
그래서 자연스럽게 부모와 자식만 비교하는 재귀 코드를 작성했다.

if (root.left != null && root.left.val < root.val)
if (root.right != null && root.right.val > root.val)

 
겉보기에는 맞는 것처럼 보였고, 간단한 테스트 케이스들도 잘 통과했다.
 
하지만 이 접근에는 치명적인 함정이 있었다.

---

 

❌ 왜 이 방식은 틀렸을까?

BST의 조건은
“부모와 자식” 관계만의 문제가 아니다.

 

• 자식 노드만 부모와 비교하면
• 조상 노드와의 관계를 놓치게 된다
• 그래서 겉보기엔 맞아 보이지만 틀린 코드가 된다

중요한 건,

왼쪽 / 오른쪽 서브트리 전체가 조건을 만족해야 한다는 점이다.

 

반례

    5
   / \
  3   7
     /
    4

 

• 4 < 7 → 자식 기준으로는 정상
• 하지만 4 < 5 → BST 조건 위반

즉, 👉 자식만 비교하면, 조상 노드와의 관계를 놓치게 된다.

 

이 순간 깨달았다.

“이건 단순 비교 문제가 아니라
값의 범위를 관리해야 하는 문제구나.”

---

💡 핵심 깨달음: 범위(min, max)

각 노드는 조상들로부터 허용된 값의 범위를 가지고 있다.

• 왼쪽으로 내려가면 → max가 줄어들고
• 오른쪽으로 내려가면 → min이 커진다

그래서 함수의 의미를 이렇게 정의했다.

• validate(node, min, max)
  • 현재 노드 값이 (min, max) 범위 안에 있는지 검사

---

 

코드 (Java) - 범위(min / max) 방식

class Solution {
    public boolean isValidBST(TreeNode root) {
        return validate(root, null, null);
    }

    private boolean validate(TreeNode node, Integer min, Integer max) {
        if (node == null) return true;

        if (min != null && node.val <= min) return false;
        if (max != null && node.val >= max) return false;

        return validate(node.left, min, node.val)
            && validate(node.right, node.val, max);
    }
}

 

📈 Time / Space Complexity

• Time: 모든 노드를 한 번씩 방문 → O(N)
• Space: 재귀 호출 스택 → O(H)
  (H = 트리 높이, 최악의 경우 O(N))

---

 

🔹 다른 접근: Inorder Traversal

BST의 또 다른 중요한 성질은 중위 순회 결과가 항상 오름차순이라는 점이다.

 

중위 순회가 뭐길래?

 

중위 순회(Inorder Traversal)는 노드를 방문하는 순서가 왼쪽 → 현재 → 오른쪽 이다.

BST에서 이 순서로 탐색하면, 작은 값 → 큰 값 → 더 큰 값 즉, 정렬된 숫자처럼 나와야 한다.

 

예시

정상적인 BST

    2
   / \
  1   3


중위 순회 결과: 1 → 2 → 3

 

BST가 아닌 경우

    5
   / \
  1   4
     / \
    3   6

중위 순회 결과: 1 → 5 → 3 → 4 → 6

 

5 → 3 으로 값이 갑자기 작아진다.

 

그래서 검사 방법은 이렇게 바뀐다

• 👉 “이 노드의 오른쪽이 큰가?” 를 검사하는 게 아니라
• 👉 “지금 값이 이전 값보다 큰가?” 만 확인한다.

이전 값보다 작아지는 순간 → BST가 아니다.

 

 

이 성질을 이용하면 다음과 같이 풀 수도 있다.

class Solution {
    Integer prev = null;

    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;

        // 1. 왼쪽 끝까지 간다
        if (!isValidBST(root.left)) return false;

        // 2. 이전 값보다 작아지면 실패
        if (prev != null && root.val <= prev) return false;

        // 3. 현재 값을 이전 값으로 저장
        prev = root.val;

        // 4. 오른쪽으로 이동
        return isValidBST(root.right);
    }
}

 

 

"오른쪽이 큰지" 왜 안 보나요?

중위 순회에서는 오른쪽 노드들이 항상 현재 노드 이후에 방문된다.

만약 오른쪽에 더 작은 값이 있다면

• → 순서가 깨지고
• → root.val <= prev 에서 자동으로 걸린다.

즉,

오른쪽이 크다는 조건은
순서 자체로 이미 검증되고 있다.

 

---

 

📝 이번 문제에서 얻은 깨달음

• BST 검증은 부모–자식 비교 문제가 아니다
• 핵심은 👉 “이 노드는 어떤 범위 안의 값을 가질 수 있는가?”
• 트리 문제에서 값 비교가 나오면
  범위(min/max)를 관리하고 있는지부터 의심해보자