#include "stdafx.h"
#include <iostream>

using namespace std;

struct elem { //структура на дървото
    int key;  //стойност на елемента
    elem* left; // ляво поддърво
    elem* right; //дясно поддърво
    bool printed = false; //дали елемента е принтиран
} *root = NULL; // инициализация на корена


void obhozdane(elem *t);
void add(int n, elem *&t);

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

    while (broj < 1) { //ако потребителя въведе число по-малко от 1 за брой, накарай го да въвежда пак число
        cout << "Nevaliden broj" << endl;
        cout << "Broj elementi: ";
        cin >> broj;
    }

    int number; //елемент на дървото
    cout << "Vavedete elementi: " << endl;

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

    obhozdane(root);
}


//obhozdane prav red - корен, lqvo poddarvo dqsno poddarvo
void obhozdane(elem *t) //t -  цялото дърво или поддърво
{
    if (t)
    {
        obhozdane(t->left);
        obhozdane(t->right);

        if (t->left != NULL && t->left->left == NULL && t->printed == false) { //върха преди листо, за лявата страна
            cout << t->key << "\t";
            t->printed = true;
        }
        if (t->right != NULL && t->right->right == NULL && t->printed == false) { //върха преди листо, за дясната страна
            cout << t->key << "\t";
            t->printed = true;
        }
    }
}

void add(int n, elem *&t)
{
    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);
        }
    }
}