Kiểm tra cây nhị phân có phải BST trong C

BST (Binary Search Tree): cây nhị phân mà nút trái < gốc < nút phải, áp dụng đệ quy cho mọi cây con.

Thuật toán

Duyệt đệ quy với khoảng giá trị cho phép [min, max]. Gốc ban đầu: [INT_MIN, INT_MAX].

Chương trình

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

struct Node {
    int data;
    Node *left, *right;
    Node(int d) : data(d), left(NULL), 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);
    
    cout << (isBST(root) ? "La BST" : "Khong phai BST");
    return 0;
}

Kết quả

La BST