#include <vector>
#include <iostream>

using namespace std;
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

//generate BST from elements of num in range [low, high)
TreeNode *sortedArrayToBST(vector<int> &num, int low, int high) {
    if (low >= high) return NULL;
    
    int mid = (high-low)/2 + low;
    TreeNode *n = new TreeNode(num[mid]);
    
    n->left = sortedArrayToBST(num, low, mid);
    n->right = sortedArrayToBST(num, mid+1, high);
    
    return n;
}

TreeNode *sortedArrayToBST(vector<int> &num) {
    return sortedArrayToBST(num, 0, num.size());
}

void preorderPrintTree(TreeNode *n) {
    if (n == NULL) {
        cout << "#, ";
        return;
    }
    
    cout << n->val << ", ";
    preorderPrintTree(n->left);
    preorderPrintTree(n->right);
}

int main (int argc, const char * argv[]) {
    
    int a[] = {0,1,2};
    vector<int> va(a, a+sizeof(a)/sizeof(int));
    preorderPrintTree(sortedArrayToBST(va));
    cout << endl;
    
    int b[] = {0,1,2,3,4,5,6,7,8,9};
    vector<int> vb(b, b+sizeof(b)/sizeof(int));
    preorderPrintTree(sortedArrayToBST(vb));
    cout << endl;
    return 0;
}


// Output:
// 1, 0, #, #, 2, #, #, 
// 5, 2, 1, 0, #, #, #, 4, 3, #, #, #, 8, 7, 6, #, #, #, 9, #, #,