#include <iostream>

using namespace std;

struct elem {
    int key;
    elem* left;
    elem* right;
} *root = NULL;


bool found(elem *t, int n);
void add(int n, elem *&t);
void preorder(elem *t);
void inorder(elem *t);
void postorder(elem *t);


void main()
{
    int broj;
    cout << "Broj elementi: ";
    cin >> broj;

    int number;
    cout << "Vavedete elementi: " << endl;

    for    (int i = 0; i < broj; i++)
    {
        cin >> number;
        add(number, root);
    }

    preorder(root);
}


//obhozdane prav red - корен, lqvo poddarvo dqsno poddarvo
void preorder(elem *t)
{
    if(t)
    {
        cout << t->key << "\t";
        preorder(t->left);
        preorder(t->right);
    }
}

//obhozdane vatreshen red - vqvo poddarvo, koren, dqsno
void inorder(elem *t)
{
    if(t)
    {
        inorder(t->left);
        cout << t->key << "\t";
        inorder(t->right);
    }
}

//obhozdane v obraten red - lqvo poddarvo dqsno poddarvo koren
void postorder(elem *t)
{
    if(t)
    {
        postorder(t->left);
        postorder(t->right);
        cout << t->key << "\t";
    }
}


//1 6 9 7 1


void add(int n, elem *&t) //dobavqne na listo
{
    if(t == NULL)
    {
        t = new elem;
        t->key = n;
        t->left = t->right = NULL;
    }
    else
    {
        if(t->key < n)
        {
            add(n, t->right);
        }
        else
        {
            add(n, t->left);
        }
    }
}

bool found(elem *t, int n)
{
    if(t)
    {

        if(t->key == n)
        {
            return true;
        }

        cout << t->key << "\t";
        preorder(t->left);
        preorder(t->right);

        return false;
    }

    return false;
}