JavaScript로 이진 탐색 트리(BST)에서 최소 절대 차이 구하기

문제 소개

숫자 데이터를 담고 있는 이진 탐색 트리(Binary Search Tree, BST)의 루트 노드를 입력으로 받는 JavaScript 함수를 작성해야 합니다. 예를 들어 다음과 같은 트리가 있다고 가정해 보겠습니다.

1
 \
  3
 /
2

이때 함수는 트리에 있는 임의의 두 노드 값 사이의 최소 절대 차이(최소 절댓값 차이)를 반환해야 합니다.

위 트리의 경우 출력 결과는 다음과 같습니다.

const output = 1;

그 이유는 |1 - 2| = |3 - 2| = 1 이기 때문입니다. 즉, 두 노드 값의 차이 중 가장 작은 값이 1입니다.

접근 방법: 중위 순회(In-order Traversal) 활용

이 문제를 효율적으로 해결하는 핵심은 BST의 특성에 있습니다. 이진 탐색 트리를 중위 순회(in-order traversal)하면 노드 값들이 오름차순으로 정렬된 배열을 얻을 수 있습니다.

정렬된 배열에서 최소 절대 차이는 반드시 인접한 두 원소 사이에서 발생하므로, 순회 결과를 배열에 저장한 뒤 인접한 값들의 차이만 비교하면 됩니다. 이 방법은 모든 노드 쌍을 비교하는 O(n²) 방식보다 훨씬 효율적인 O(n) 시간 복잡도로 문제를 해결할 수 있습니다.

구현 예제

BST 클래스를 정의하고, 중위 순회를 통해 최소 절대 차이를 구하는 전체 코드는 다음과 같습니다.

class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor() {
        // 이진 탐색 트리의 루트
        this.root = null;
    }

    insert(data) {
        const newNode = new Node(data);
        if (this.root === null) {
            this.root = newNode;
        } else {
            this.insertNode(this.root, newNode);
        }
    }

    insertNode(node, newNode) {
        if (newNode.data < node.data) {
            if (node.left === null) {
                node.left = newNode;
            } else {
                this.insertNode(node.left, newNode);
            }
        } else {
            if (node.right === null) {
                node.right = newNode;
            } else {
                this.insertNode(node.right, newNode);
            }
        }
    }
}

const BST = new BinarySearchTree();
BST.insert(1);
BST.insert(3);
BST.insert(2);

const getMinimumDifference = function(root) {
    const nodes = [];

    // 중위 순회: 왼쪽 → 루트 → 오른쪽 순서로 방문
    const dfs = (root) => {
        if (root) {
            dfs(root.left);
            nodes.push(root.data);
            dfs(root.right);
        }
    };

    dfs(root);

    // 정렬된 배열에서 인접한 값들의 차이 중 최솟값 찾기
    let result = nodes[1] - nodes[0];
    for (let i = 1; i < nodes.length - 1; i++) {
        result = Math.min(result, nodes[i + 1] - nodes[i]);
    }
    return result;
};

console.log(getMinimumDifference(BST.root));

실행 결과

위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.

1

코드 설명

1. Node 클래스: 각 노드는 data(값), left(왼쪽 자식), right(오른쪽 자식) 세 가지 속성을 가집니다.

2. BinarySearchTree 클래스: insert 메서드와 insertNode 메서드를 통해 새로운 값을 BST 규칙(왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큼)에 맞게 삽입합니다.

3. getMinimumDifference 함수:

• dfs 재귀 함수가 중위 순회를 수행하여 노드 값을 nodes 배열에 오름차순으로 저장합니다.
• 배열이 정렬되어 있으므로 인접한 두 원소의 차이(nodes[i + 1] - nodes[i])만 확인하면 됩니다.
• Math.min을 사용해 최소 차이를 갱신한 후 반환합니다.

이처럼 BST의 정렬된 순회 특성을 활용하면, 모든 노드 쌍을 일일이 비교하지 않고도 선형 시간 안에 최소 절대 차이를 효율적으로 구할 수 있습니다.