Leetcode 783. Minimum Distance Between BST Nodes
이진 탐색 트리 노드 간 값 차이의 최솟값 구하는 문제

난이도가 Easy이지만 평소보다 더 헤맨 문제이다
그동안 BST의 의미만 알았지 BST를 잘 이해하고 있지 않았다는 걸 깨달았다.
그만큼 BST에 대한 이해도를 올려준 문제이다.

1️⃣ 잘못 푼 코드

부모 자식 간의 관계에서만 최솟값이 나올 거라고 오산하여 이렇게 코드를 작성하였다.

class Solution {
    public int minDiffInBST(TreeNode root) { 
        return minDiff(root);
    }
    public int minDiff(TreeNode node) {
        int lDiff = Integer.MAX_VALUE, rDiff = Integer.MAX_VALUE;
        if (node == null) return Integer.MAX_VALUE;
        if (node.left == null && node.right == null) return Integer.MAX_VALUE;

        if (node.left != null)
            lDiff = Math.min(Math.abs(node.val - node.left.val), minDiff(node.left));

        if (node.right != null)
            rDiff = Math.min(Math.abs(node.val - node.right.val), minDiff(node.right));

        return Math.min(lDiff, rDiff);
    }
}

2️⃣ 풀었지만 찜찜한 코드

우선순위 큐를 활용하여 풀고 Accepted 된 코드이지만 문제 의도와 안맞는 듯한 코드이다.

// leetcode에서 Runtime 1ms, Beats 10.31% / Memory 41.43 MB, Beats 38.33%
class Solution {
    public int minDiffInBST(TreeNode root) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        dfs(root, pq);
        int pq_size = pq.size();
        int fstValue = pq.poll();
        int diff;
        int minDiff = Integer.MAX_VALUE;
        for (int i = 0; i<pq_size-1; i++) {
            int cur = pq.poll();
            diff = cur - fstValue;
            if (minDiff > diff) minDiff = diff;
            fstValue = cur;
        }
        return minDiff;
    }
    private void dfs(TreeNode node, PriorityQueue<Integer> pq) {
        pq.add(node.val);
        if (node.left != null) dfs(node.left, pq);
        if (node.right != null) dfs(node.right, pq);
    }
}

3️⃣ 책 코드

1. 재귀 구조로 중위 순회

// leetcode에서 Runtime 0ms, Beats 100.00% / Memory 41.06 MB,  Beats 90.92%
class Solution {
    // 이전 노드의 값, 가장 작은 수로 설정
    // +100000은 오버플로 방지를 위한 방편 🟠
    int prev = Integer.MIN_VALUE + 100000;
    // 노드 간 차이 최솟값, 가장 큰 수로 설정
    int minDiff = Integer.MAX_VALUE;

    public int minDiffInBST(TreeNode root) {
        // 왼쪽 자식 노드 맨 아래까지 탐색
        if (root.left != null) minDiffInBST(root.left);
        // 현재 노드 값과 이전 노드 값의 차이를 구하고 최솟값인지 확인
        minDiff = Math.min(minDiff, root.val - prev);
        prev = root.val;
        
        // 오른쪽 자식 노드 재귀 탐색
        if (root.right != null) minDiffInBST(root.right);
        return minDiff;
    }
}

Constraints:

The number of nodes in the tree is in the range [2, 100].
0 <= Node.val <= 10^5

🔹 매직 넘버 ( 코드의 100000 )

🟠 minDiff = Math.min(minDiff, root.val - prev);에서 minDiff나 root.val - prev 값이 살아남을 리 없도록 최댓값으로 맞춰 준 것이다.

이렇게 하면 문제의 제약 조건 상 이전 노드 값과 현재 노드 값의 차이는 최대 10^5이라 계속되는 Math.min()에서 첫 비교 값이 살아남을 확률은 없다.

한편, prev = Integer.MIN_VALUE에 10^5를 더해 준 이유는 Node.val의 최댓값이 10^5이니 root.val - prev에서 오버플로가 나지 않도록 하기 위해서이다.

// 위 코드 4번째 줄   // 이전 노드의 값, 가장 작은 수로 설정.
int prev = Integer.MIN_VALUE + 100000;

이런 100000을 매직 넘버라고 부른다.

⚠️ 하지만 엄밀히 따져 봤을 때 10^5를 더해도 오버플로가 날 수 있다.
root.val - prev = root.val - (Integer.MIN_VALUE + 10^5)
                = root.val - Integer.MIN_VALUE - 10^5

이 상황에서 root.val이 최댓값인 10^5이라면,
root.val - prev = - Integer.MIN_VALUE
                = Integer.MAX_VALUE + 1 이다.‼️

(Java의 int 범위는 Integer.MIN_VALUE = -2_147_483_648
                  Integer.MAX_VALUE = 2_147_483_647 이므로)
                 
그러므로 이 코드는 경계값에서 오버플로 터질 수 있다.
이를 방지하려면 버퍼 용도의 매직 넘버를 10^5+1로 써야 했다.
                 

이 매직 넘버는 문제의 제약에 의존하기 때문에 범위가 바뀌면 다시 깨질 수 있어서 안전하지 않다. 그러니 실무에서는 아래와 같이 prev를 null이나 boolean 플래그로 관리해서 첫 비교를 건너뛰는 방법이 더 명확하고 안전하다.

매직 넘버를 쓰지 않고 첫 비교를 스킵 처리한 예시

// 👉 `null`로
class Solution {
    Integer prev = null; // 이전 노드 값 (처음엔 없음)
    int minDiff = Integer.MAX_VALUE;

    public int minDiffInBST(TreeNode root) {
        // 왼쪽 서브트리 탐색
        if (root.left != null) {
            minDiffInBST(root.left);
        }

        // 이전 노드가 있을 때만 차이 계산
        if (prev != null) {
            minDiff = Math.min(minDiff, root.val - prev);
        }
        prev = root.val; // 현재 노드 값을 prev로 저장

        // 오른쪽 서브트리 탐색
        if (root.right != null) {
            minDiffInBST(root.right);
        }

        return minDiff;
    }
}

// 👉 `boolean flag`로
class Solution {
    int prev;
    boolean hasPrev = false;
    int minDiff = Integer.MAX_VALUE;

    public int minDiffInBST(TreeNode root) {
        if (root == null) return minDiff;
        if (root.left != null) minDiffInBST(root.left);

        if (hasPrev) {
        	// 오버플로 보수적으로 막으려면 long 사용
            int diff = root.val - prev;
            minDiff = Math.min(minDiff, diff);
        }
        prev = root.val;
        hasPrev = true;

        if (root.right != null) minDiffInBST(root.right);
        return minDiff;
    }
}