พิมพ์คีย์ BST ในช่วงที่กำหนด [k1, k2] ใน C++

โจทย์

ให้ Binary Search Tree (BST) และช่วง k1 ถึง k2 ต้องการพิมพ์คีย์ทั้งหมดที่อยู่ในช่วง [k1, k2] เรียงจากน้อยไปมาก

คุณสมบัติ BST

• Left subtree มีค่าน้อยกว่า Root
• Right subtree มีค่ามากกว่า Root
• ทุก Subtree ก็เป็น BST

วิธีแก้ปัญหา

ใช้ Inorder Traversal แบบ Recursive พร้อมเงื่อนไขตัดกิ่ง:

1. ถ้า root > k1 → เรียกซ้าย
2. ถ้า k1 ≤ root ≤ k2 → พิมพ์ root
3. ถ้า root < k2 → เรียกขวา

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class node {
public:
    int data;
    node *left;
    node *right;
};

void nodesInRange(node *root, int k1, int k2) {
    if (NULL == root) return;
    if (k1 < root->data) nodesInRange(root->left, k1, k2);
    if (k1 <= root->data && k2 >= root->data) cout << root->data << "\t";
    if (k2 > root->data) nodesInRange(root->right, k1, k2);
}

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

int main() {
    node *root = new node();
    int k1 = 12, k2 = 25;
    root = insert(20);
    root->left = insert(10);
    root->right = insert(24);
    root->left->left = insert(8);
    root->left->right = insert(15);
    root->right->right = insert(32);
    cout << "The values of node within the range are\t";
    nodesInRange(root, k1, k2);
    return 0;
}

ผลลัพธ์

The values of node within the range are 15 20 24