#include <iostream>
using namespace std;

// Struktura drzewa BST
struct ele {
    int dane;
    ele* lewy;
    ele* prawy;
};

// Funkcja tworząca nowy węzeł
ele* stworzWezel(int dane) {
    ele* nowy = new ele();
    nowy->dane = dane;
    nowy->lewy = nullptr;
    nowy->prawy = nullptr;
    return nowy;
}

// Funkcja wstawiająca nowy element do drzewa BST
ele* wstawBST(ele* korzen, int dane) {
    if (korzen == nullptr) {
        return stworzWezel(dane);
    }
    if (dane < korzen->dane) {
        korzen->lewy = wstawBST(korzen->lewy, dane);
    } else {
        korzen->prawy = wstawBST(korzen->prawy, dane);
    }
    return korzen;
}

// Funkcja wyszukująca element w drzewie BST
ele* wyszukaj(ele* korzen, int klucz) {

}

// Funkcja przechodząca drzewo BST w porządku INORDER (dla sprawdzenia poprawności)
void przejdzInorder(ele* korzen) {
    if (korzen != nullptr) {
        przejdzInorder(korzen->lewy);
        cout << korzen->dane << " ";
        przejdzInorder(korzen->prawy);
    }
}

int main() {
    int liczby[] = {2, 1, 30, 10, 5, 4, 11, 18, 7, 40};
    int rozmiar = sizeof(liczby) / sizeof(liczby[0]);

    ele* korzen = nullptr;

    // Tworzenie drzewa BST
    for (int i = 0; i < rozmiar; ++i) {
        korzen = wstawBST(korzen, liczby[i]);
    }

    // Wyświetlenie drzewa w porządku INORDER
    cout << "Drzewo BST w porządku INORDER: ";
    przejdzInorder(korzen);
    cout << endl;

    // Wyszukiwanie elementu w drzewie
    int klucz;
    cout << "Podaj klucz do wyszukania: ";
    cin >> klucz;

    ele* wynik = wyszukaj(korzen, klucz);
    if (wynik != nullptr) {
        cout << "Znaleziono element o wartości: " << wynik->dane << endl;
    } else {
        cout << "Element o podanym kluczu nie istnieje w drzewie." << endl;
    }

    return 0;
}