#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstdlib>

using namespace std;

struct Node {
    int value;
    int left, right;
    Node(int value_ = 0, int left_ = -1, int right_ = -1) :
        value(value_), left(left_), right(right_) {}
};

int root;
vector <Node> tree;
vector <int> values;

int buildTree(int L, int R) {
    // -1 of Node.left or Node.right means no child
    if (R < L)
        return -1;

    int pivot = values[R];
    int idx = L;
    for (int i = L; i < R; i++) {
        if (values[i] < pivot) {
            swap(values[i], values[idx]);
            idx++;
        }
    }
    swap(values[idx], values[R]);
    
    tree.push_back(Node(values[idx]));
    int curNodeIdx = (int)tree.size() - 1;
    tree[curNodeIdx].left = buildTree(L, idx - 1);
    tree[curNodeIdx].right = buildTree(idx + 1, R);
    return curNodeIdx;
}

void printTree(int node) {
    if (node == -1)
        return;
    printTree(tree[node].left);
    fprintf(stderr, "%d\n", tree[node].value);
    printTree(tree[node].right);
}

int main(void) {
    srand(42);
    for (int i = 0; i < 10; i++)
        values.push_back(rand() % 101);

    fprintf(stderr, "Building binary search tree out of values: {");
    for (int i = 0; i < (int)values.size(); i++) {
        fprintf(stderr, "%d%s", values[i], i + 1 == (int)values.size() ? "}\n" : ", ");
    }
    
    //tree.reserve(values.size());
    root = buildTree(0, (int)values.size() - 1);
    fprintf(stderr, "Root is: %d\n", root);
    printTree(root);
    
    return 0;
}