Java로 균형 이진 탐색 트리(BST)에서 주어진 합을 만족하는 쌍 찾기

개념

균형 잡힌 이진 탐색 트리(Balanced BST)와 목표 합계(target sum)가 주어졌을 때, 두 노드 값의 합이 목표 합계와 같은 쌍이 존재하면 true를, 존재하지 않으면 false를 반환하는 함수를 작성하는 문제입니다. 이 문제에서 요구되는 조건은 다음과 같습니다.

• 시간 복잡도: O(n)
• 허용되는 추가 공간: O(log n)
• BST 구조 자체는 수정 불가

참고로 균형 BST의 높이는 항상 O(log n)이라는 점을 기억해 두면 좋습니다.

예시

접근 방법

1. 브루트 포스(완전 탐색)

BST의 모든 노드 쌍을 하나씩 검사하여 합이 X와 같은지 확인하는 가장 단순한 방식입니다. 구현은 쉽지만 시간 복잡도가 O(n²)으로 비효율적입니다.

2. 중위 순회 + 투 포인터

더 나은 방법은 보조 배열을 만들어 BST의 중위 순회(Inorder Traversal) 결과를 저장하는 것입니다. 중위 순회는 항상 정렬된 순서로 노드를 방문하므로, 배열은 오름차순으로 정렬된 상태가 됩니다. 정렬된 배열에서는 양쪽 끝에서 시작하는 투 포인터(Two Pointer) 기법을 활용해 O(n) 시간 안에 원하는 쌍을 찾을 수 있습니다.

다만 이 방법은 O(n)의 실행 시간을 가지지만, O(n) 크기의 보조 배열이 필요하다는 점에 유의해야 합니다.

Java 구현 코드

// Java 코드: 균형 BST에서 주어진 합계를 가진 쌍 찾기
import java.util.ArrayList;

// 이진 트리 노드
class Node1 {
    int data1;
    Node1 left1, right1;
    Node1(int d){
        data1 = d;
        left1 = right1 = null;
    }
}

public class BinarySearchTree {
    // BST의 루트 노드
    Node1 root1;

    // 생성자
    BinarySearchTree(){
        root1 = null;
    }

    // 트리의 중위 순회
    void inorder(){
        inorderUtil1(this.root1);
    }

    // 중위 순회를 위한 유틸리티 함수
    void inorderUtil1(Node1 node1){
        if (node1 == null)
            return;
        inorderUtil1(node1.left1);
        System.out.print(node1.data1 + " ");
        inorderUtil1(node1.right1);
    }

    // insertRec()을 호출하는 메서드
    void insert(int key1){
        root1 = insertRec1(root1, key1);
    }

    /* BST에 새로운 키를 삽입하는 재귀 함수 */
    Node1 insertRec1(Node1 root1, int data1){
        // 트리가 비어 있으면 새 노드를 반환
        if (root1 == null) {
            root1 = new Node1(data1);
            return root1;
        }
        // 그렇지 않으면 트리를 따라 아래로 재귀 진행
        if (data1 < root1.data1)
            root1.left1 = insertRec1(root1.left1, data1);
        else if (data1 > root1.data1)
            root1.right1 = insertRec1(root1.right1, data1);
        return root1;
    }

    // 주어진 BST의 값을 ArrayList에 담아 반환하는 메서드
    ArrayList<Integer> treeToList(Node1 node1, ArrayList<Integer> list1){
        // 기저 사례(Base Case)
        if (node1 == null)
            return list1;
        treeToList(node1.left1, list1);
        list1.add(node1.data1);
        treeToList(node1.right1, list1);
        return list1;
    }

    // 쌍이 존재하는지 확인하는 메서드
    boolean isPairPresent(Node1 node1, int target1){
        // a1 리스트는 treeToList 메서드에 인자로 전달되며,
        // 이후 BST의 값들로 채워집니다.
        ArrayList<Integer> a1 = new ArrayList<>();
        // a2 리스트에는 treeToList 메서드가 반환한
        // BST의 모든 값이 담깁니다.
        ArrayList<Integer> a2 = treeToList(node1, a1);

        int start1 = 0;             // a2의 시작 인덱스
        int end1 = a2.size() - 1;   // a2의 끝 인덱스

        while (start1 < end1) {
            if (a2.get(start1) + a2.get(end1) == target1) { // 목표 합 발견!
                System.out.println("Pair Found: " + a2.get(start1) + " + " + a2.get(end1) + " " + "= " + target1);
                return true;
            }
            if (a2.get(start1) + a2.get(end1) > target1)
                end1--;    // 합이 크면 끝 인덱스 감소
            if (a2.get(start1) + a2.get(end1) < target1)
                start1++;  // 합이 작으면 시작 인덱스 증가
        }
        System.out.println("No such values are found!");
        return false;
    }

    // 드라이버 함수
    public static void main(String[] args){
        BinarySearchTree tree1 = new BinarySearchTree();
        /*
          16
         /  \
       11    21
      /  \   /  \
     9   13 17  26 */
        tree1.insert(16);
        tree1.insert(11);
        tree1.insert(21);
        tree1.insert(9);
        tree1.insert(13);
        tree1.insert(17);
        tree1.insert(26);
        tree1.isPairPresent(tree1.root1, 34);
    }
}

실행 결과

Pair Found: 13 + 21 = 34

목표 합계 34를 만족하는 쌍 13 + 21이 성공적으로 발견되었습니다.

복잡도 분석

• 시간 복잡도: O(n) — 중위 순회로 배열을 채우는 데 O(n), 투 포인터 탐색에 O(n)
• 공간 복잡도: O(n) — 중위 순회 결과를 저장하는 보조 ArrayList가 필요