Đếm nút BST trong khoảng cho trước trong C++

Cho cây tìm kiếm nhị phân (BST) và khoảng [low, high]. Đếm số nút có giá trị nằm trong khoảng này.

Ví dụ

BST với các nút: 10, 14, 19, 27, 31, 35, 42. Khoảng [11, 40] → 5 nút (14, 19, 27, 31, 35).

Phương pháp (Đệ quy, tận dụng tính chất BST)

• Nếu root NULL → 0.
• Nếu root->data trong [low, high]: 1 + đệ quy trái + đệ quy phải.
• Nếu root->data < low: chỉ đệ quy phải (cây phải toàn giá trị lớn hơn).
• Nếu root->data > high: chỉ đệ quy trái (cây trái toàn giá trị nhỏ hơn).

Ví dụ minh họa (C++)

#include <iostream>
using namespace std;

struct node {
    int data;
    struct node* left, *right;
};

node* newNode(int data) {
    node* temp = new node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

int findcount(node* root, int low, int high) {
    if (!root) return 0;
    if (root->data == high && root->data == low) return 1;
    if (root->data <= high && root->data >= low) {
        return 1 + findcount(root->left, low, high) + findcount(root->right, low, high);
    } else if (root->data < low) {
        return findcount(root->right, low, high);
    } else {
        return findcount(root->left, low, high);
    }
}

int main() {
    node* root = newNode(27);
    root->left = newNode(14);
    root->right = newNode(35);
    root->left->left = newNode(10);
    root->left->right = newNode(19);
    root->right->left = newNode(31);
    root->right->right = newNode(42);
    int low = 10, high = 50;
    cout << "Count of nodes between [" << low << ", " << high << "] is " << findcount(root, low, high);
    return 0;
}

Đầu ra

Count of nodes between [10, 50] is 7