#include <iostream>
#include <fstream>
#include <vector>
#include <queue>


// _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
// _ _ _ СТРУКТУРА УЗЛА ДЕРЕВА _ _ _
// _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
struct Node {
    int key;
    Node* left = nullptr;
    Node* right = nullptr;
    Node(int key, Node* left, Node* right) {
        this->key = key;
        this->left = left;
        this->right = right;
    }
};

//_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
// _ _ _ ФУНКЦИИ ОБРАБОТКИ ВЕКТОРА И ДЕРЕВА _ _ _
//_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
Node* addNode(int key, Node* left, Node* right) {
    Node* node = new Node(key, left, right);
    return node;
}


int midOfVector(int start, int end) {
    return start + (end - start) / 2;
}


Node* vectorToBST(std::vector <int> vector, int start, int end);

Node* newRoot(std::vector<int> vector, int start, int end) {
    return addNode(vector[midOfVector(start, end)],vectorToBST(vector, start, midOfVector(start, end) - 1), vectorToBST(vector, midOfVector(start, end) + 1, end));
}

void exit() { return; }

Node* vectorToBST(std::vector <int> vector, int start, int end) {
    return start > end ? nullptr : newRoot(vector, start, end);
}

//int vectorSize(vector <int> vector) {
//    return vector.size();
//}

//_ _ _ _ _ _ _ _ _ _ _ _ _ _
// _ _ _ ЧТЕНИЕ С ФАЙЛА _ _ _
//_ _ _ _ _ _ _ _ _ _ _ _ _ _
std::vector<int> readFile() {
    std::ifstream fin("input6.txt");
    std::vector<int> data;
    std::copy(std::istream_iterator<int>(fin), std::istream_iterator<int>(), std::back_inserter<std::vector<int> >(data));
    return data;
}

// _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
// _ _ _ ВЫВОД ЧЕРЕЗ BFS С QUEUE _ _ _
// _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
void recursiveBFS(Node* node, std::queue<Node*> &queueData, int amountOfKeys);

void addQueue(Node* node, std::queue<Node*> &queueData, int amountOfKeys) {
    std::cout << queueData.front()->key << " ";

    queueData.front()->left != nullptr ? queueData.push(queueData.front()->left) : queueData.push(nullptr);
    queueData.front()->right != nullptr ? queueData.push(queueData.front()->right) : queueData.push(nullptr);
    queueData.pop();

    recursiveBFS(node, queueData, amountOfKeys - 1);
}


void ifNodeNull(Node* node, std::queue<Node*> &queueData, int amountOfKeys) {
    std::cout << "null ";
    queueData.pop();
    recursiveBFS(node, queueData, amountOfKeys);
    return;
}


void recursiveBFS(Node* node, std::queue<Node*> &queueData, int amountOfKeys) {
    queueData.empty() || amountOfKeys == 0 ? exit() : queueData.front() == nullptr ? ifNodeNull(node, queueData, amountOfKeys) : addQueue(node, queueData, amountOfKeys);
}

void printTree(Node* root, int amountOfKeys) {
    std::queue<Node*> queueData;
    queueData.push(root);
    recursiveBFS(root, queueData, amountOfKeys);
}
// _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

int main(){
    std::vector<int> data = readFile();
    printTree(vectorToBST(data, 0, data.size() - 1), data.size());
    return 0;
}