program-1.cpp

/* 
TBT Creation and Preorder Traversal
*/

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node *left, *right;
    bool lthread, rthread;

    Node(int val) {
        data = val;
        left = right = NULL;
        lthread = rthread = true;
    }
};

class TBT {
    Node* root;

public:
    TBT() {
        root = NULL;
    }

    void insert(int key) {
        Node* ptr = root;
        Node* par = NULL;

        while (ptr != NULL) {
            if (key == ptr->data)
                return;

            par = ptr;

            if (key < ptr->data) {
                if (!ptr->lthread)
                    ptr = ptr->left;
                else
                    break;
            } else {
                if (!ptr->rthread)
                    ptr = ptr->right;
                else
                    break;
            }
        }

        Node* temp = new Node(key);

        if (par == NULL) {
            root = temp;
            temp->left = temp->right = NULL;
        } else if (key < par->data) {
            temp->left = par->left;
            temp->right = par;
            par->lthread = false;
            par->left = temp;
        } else {
            temp->left = par;
            temp->right = par->right;
            par->rthread = false;
            par->right = temp;
        }
    }

    void preorder() {
        Node* cur = root;

        while (cur != NULL) {
            cout << cur->data << " ";

            if (!cur->lthread)
                cur = cur->left;
            else if (!cur->rthread)
                cur = cur->right;
            else {
                while (cur != NULL && cur->rthread)
                    cur = cur->right;

                if (cur != NULL)
                    cur = cur->right;
            }
        }
    }
};

int main() {
    TBT t;
    int n, x;

    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> x;
        t.insert(x);
    }

    t.preorder();

    return 0;
}