#include <iostream>
#include <vector>
using namespace std;

struct Node {
    int key;
    int value; // Folosim value pentru a stoca frecvența
    Node* left;
    Node* right;
    
    Node(int k) : key(k), value(1), left(nullptr), right(nullptr) {}
};

class BSTMap {
private:
    Node* root;

    // Inserare recursivă, creștem valoarea (frecvența) dacă cheia există
    Node* insert(Node* node, int key) {
        if (!node) return new Node(key);
        if (key < node->key) 
            node->left = insert(node->left, key);
        else if (key > node->key) 
            node->right = insert(node->right, key);
        else 
            node->value++; // Creștem frecvența dacă cheia există
        return node;
    }

    // Căutare recursivă
    Node* search(Node* node, int key) {
        if (!node || node->key == key) return node;
        if (key < node->key) return search(node->left, key);
        return search(node->right, key);
    }

    // Parcurgere in-order pentru a afișa frecvențele
    void inorder(Node* node) {
        if (!node) return;
        inorder(node->left);
        std::cout << node->key << " appears " << node->value << " times\n";
        inorder(node->right);
    }

public:
    BSTMap() : root(nullptr) {}

    // Funcție publică pentru inserare
    void insert(int key) {
        root = insert(root, key);
    }

    // Funcție publică pentru a obține frecvența
    int get(int key) {
        Node* node = search(root, key);
        return node ? node->value : 0; // 0 dacă cheia nu există
    }

    // Afișarea frecvențelor
    void print() {
        inorder(root);
    }
};

int main() {
    std::vector<int> arr = {7, 8, 8, 8, 7, 5, 55, 55, 101, 4, 7, 101, 1, 4};

    BSTMap myMap;
    
    // Inserăm fiecare element din array în arbore
    for (int num : arr) {
        myMap.insert(num);
    }

    // Afișăm frecvențele
    myMap.print();

    return 0;
}