C++로 BST에서 주어진 범위 내의 하위 트리 개수 구하기

이진 탐색 트리(Binary Search Tree, BST)가 입력으로 주어졌을 때, 모든 노드의 값이 특정 범위(start ~ end) 안에 속하는 하위 트리(subtree)의 개수를 구하는 것이 목표입니다. 예를 들어 start가 5이고 end가 50이라면, BST에서 모든 노드의 값이 5 이상 50 이하인 하위 트리의 개수를 세어야 합니다.

예제

입력 1

아래와 같은 트리와 범위 [3-6]이 주어집니다.

출력 − 범위 내에 있는 트리 개수 − 2

설명 − 노드 4와 6만 해당됩니다. 이 노드들의 하위 트리(NULL)는 모두 3~6 사이에 있기 때문입니다.

입력 2

아래와 같은 트리와 범위 [12-20]이 주어집니다.

C++로 BST에서 주어진 범위 내의 하위 트리 개수 구하기

출력 − 범위 내에 있는 트리 개수 − 3

설명 − 노드 16, 14, 20이 해당됩니다. 이 노드들을 루트로 하는 하위 트리 전체가 12~20 사이에 있습니다.

프로그램에서 사용된 접근 방식

구조체 Btreenode는 트리의 노드를 생성하는 데 사용됩니다. info 부분은 정수 값을 저장하며, left와 right 포인터는 자기 참조(self-referencing) 방식으로 하위 트리를 가리킵니다.
함수 Btreenode* insert(int data)는 data를 info 값으로 갖고 left, right 포인터가 NULL인 새 노드를 생성해 반환합니다.
insert 함수를 반복 호출하여 BST를 구성합니다. 루트의 오른쪽에 노드를 추가하려면 root->right = insert(70);, 왼쪽에 추가하려면 root->left = insert(30);처럼 작성합니다.
변수 l과 h는 각각 범위의 최솟값과 최댓값을 저장합니다.
변수 count는 l과 h 사이 범위에 속하는 하위 트리의 개수를 저장하며, 초기값은 0입니다.
함수 getBtreeCount(Btreenode* root, int low, int high, int* count)는 BST의 루트, 범위의 양쪽 경계, count 변수의 주소를 매개변수로 받고, 재귀 호출이 진행될 때마다 count 값을 갱신합니다.
현재 루트가 NULL인지 먼저 검사합니다. NULL이면 트리의 일부가 아니므로 1을 반환합니다.
현재 노드에 대해 왼쪽과 오른쪽 하위 트리의 모든 노드가 주어진 범위 내에 있는지 재귀 호출로 확인합니다. 즉, getBtreeCount(root->left, low, high, count);와 getBtreeCount(root->right, low, high, count);를 호출합니다.
양쪽 하위 트리가 모두 범위 내에 있고 현재 노드의 값도 범위 안이라면, 현재 노드를 루트로 하는 트리 전체가 범위에 속하는 것입니다. if (left && right && root->info >= low && root->info <= high) 조건이 참일 때 ++*count;로 개수를 증가시키고 1을 반환합니다.
모든 재귀 호출이 끝나면 count에는 범위 내에 있는 모든 하위 트리의 총 개수가 저장됩니다.
마지막으로 count 값을 출력하여 결과를 확인합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
// A BST node
struct Btreenode {
    int info;
    Btreenode *left, *right;
};
int getBtreeCount(Btreenode* root, int low, int high, int* count){
    // Base case
    if (root == NULL)
        return 1;
        int left = getBtreeCount(root->left, low, high, count);
        int right = getBtreeCount(root->right, low, high, count);
        if (left && right && root->info >= low && root->info <= high) {
            ++*count;
        return 1;
    }
    return 0;
}
Btreenode* insert(int data){
    Btreenode* temp = new Btreenode;
    temp->info = data;
    temp->left = temp->right = NULL;
    return (temp);
}
int main(){
       /* BST for input
          50
         / \
        30  70
       / \ / \
     20 40 60 80 */
    Btreenode* root = insert(50);
    root->left = insert(30);
    root->right = insert(70);
    root->left->left = insert(20);
    root->left->right= insert(40);
    root->right->left = insert(60);
    root->right->right = insert(80);
    int l = 10;
    int h = 50;
    int count=0;
    getBtreeCount(root, l, h, &count);
    cout << "Count of subtrees lying in range: " <<count;
    return 0;
}

출력

Count of subtrees lying in range: 3