Прямий обхід дерева

Задано масив цілих чисел. Створіть з них Бінарне Дерево Пошуку. Якщо число, що вставляється в дерево, рівне поточній вершині, його варто вставляти в праве піддерево.

Реалізуйте метод PreOrder прямого обходу дерева. При прямому обході спочату відвідується корінь, потім ліве піддерево, далі праве піддерево.

Напишіть код згідно наступного інтерфейсу:

// C++
class TreeNode
{
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Tree 
{
public:
    TreeNode *head;
    Tree() : head(NULL) {};
    void Insert(int val); // Вставка числа val в Бінарне Дерево Пошуку
    void PreOrder(void); // Вивести вершини дерева в порядку прямого обходу
};

Ви можете створювати (використовувати) за необхідності додаткові методи.

Вхідні дані

Перший рядок містить число n (1 ≤ n ≤ 100). Другий рядок містить n цілих чисел.

Вихідні дані

Створіть Бінарне Дерево Пошуку з вхідних даних. Виведіть вершини дерева в порядку прямого обходу.

Приклади