#include <iostream>
using namespace std;

// Node class with encapsulated data and accessor methods
class Node {
private:
    int data;
    Node* left;
    Node* right;

public:
    // Constructor
    Node(int val) : data(val), left(nullptr), right(nullptr) {}

    // Getters
    int getData() const { return data; }
    Node* getLeft() const { return left; }
    Node* getRight() const { return right; }

    // Setters
    void setData(int val) { data = val; }
    void setLeft(Node* node) { left = node; }
    void setRight(Node* node) { right = node; }
};

// Insert function for BST
Node* insert(Node* root, int val) {
    if (root == nullptr) {
        return new Node(val);
    }

    if (val < root->getData()) {
        root->setLeft(insert(root->getLeft(), val));
    } else if (val > root->getData()) {
        root->setRight(insert(root->getRight(), val));
    }

    return root;
}

// Recursive binary search
bool binarySearch(Node* root, int target) {
    if (root == nullptr) return false;

    if (root->getData() == target) {
        return true;
    } else if (target < root->getData()) {
        return binarySearch(root->getLeft(), target);
    } else {
        return binarySearch(root->getRight(), target);
    }
}

int main() {
    Node* root = nullptr;

    // Inserting values into BST
    int values[] = {30, 15, 50, 10, 20, 40, 60};
    for (int val : values) {
        root = insert(root, val);
    }

    // Search for a value
    int target = 20;
    if (binarySearch(root, target)) {
        cout << "Found " << target << " in the BST." << endl;
    } else {
        cout << target << " not found in the BST." << endl;
    }

    return 0;
}