ตรวจสอบ Binary Tree ว่าเป็น BST หรือไม่ ในภาษา C

BST (Binary Search Tree) คือต้นไม้ไบนารีที่โหนดซ้ายมีค่าน้อยกว่าโหนดปัจจุบัน และโหนดขวามีค่ามากกว่าโหนดปัจจุบัน สำหรับทุกโหนดในต้นไม้

อัลกอริทึม

ใช้ recursion ตรวจสอบแต่ละโหนดว่าอยู่ในช่วง [min, max] ที่ถูกต้องหรือไม่ เริ่มจาก [INT_MIN, INT_MAX] แล้วลดช่วงลงเรื่อยๆ

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

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

class Node {
public:
    int data;
    Node* left;
    Node* right;
    Node(int data) {
        this->data = data;
        left = right = NULL;
    }
};

bool isBSTUtil(Node* node, int min, int max) {
    if (!node) return true;
    if (node->data < min || node->data > max) return false;
    return isBSTUtil(node->left, min, node->data - 1) &&
           isBSTUtil(node->right, node->data + 1, max);
}

bool isBST(Node* root) {
    return isBSTUtil(root, INT_MIN, INT_MAX);
}

int main() {
    Node* root = new Node(8);
    root->left = new Node(3);
    root->right = new Node(10);
    root->left->left = new Node(1);
    root->left->right = new Node(6);
    
    if (isBST(root)) cout << "Is BST";
    else cout << "Not BST";
    return 0;
}

ผลลัพธ์

Is BST