4.3 Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height.

/*
Logic1:
Recursive
Logic2:
Iterative
*/

#include <iostream>
#include <deque>
#include <vector>
#include <utility>

using namespace std;

class node;
typedef deque<node*> nodePtrDeque;
typedef vector<int> intVector;
typedef const vector<int>& constIntVectorRef;
typedef vector<int>::const_iterator constIntVectorItr;
typedef pair<constIntVectorItr, constIntVectorItr> itrPair;
typedef pair<constIntVectorItr, constIntVectorItr>* itrPairPtr;

class node
{
public:
    int val;
    node * right;
    node * left;
    node(int v):val(v), right(NULL), left(NULL){};
};

constIntVectorItr mid(constIntVectorItr s, constIntVectorItr e)
{
    if (s > e)
    {
        return e + 1;
    }
    return ((e - s) % 2) ? (s + (e - s + 1) / 2) : (s + (e - s) / 2); 
};

node * helper(constIntVectorRef vec, constIntVectorItr s, constIntVectorItr e)
{
    if (s > e)
    {
        return NULL;
    }
    else
    {
        constIntVectorItr m = mid(s, e);
        node *n = new node(*m);
        n->left  = helper(vec, s, m - 1);
        n->right = helper(vec, m + 1, e);
        return n;
    }
};

node* Logic1(constIntVectorRef vec)
{
    if (vec.empty()) return NULL;
    /*
    uniformly use iterator of C++ feature. 
    If use pointers, then do keep them consistent.
    */
    return helper(vec, vec.begin(), vec.end() - 1);
};

node* Logic2(constIntVectorRef vec)
{
    if (vec.empty()) return NULL;
    
    node *root = NULL;
    
    constIntVectorItr s = vec.begin();
    constIntVectorItr e = vec.end() - 1;
    
    vector<itrPairPtr> stack; //stack the ranges
    nodePtrDeque nstack; //stack the parent for a range
    
    stack.push_back(new itrPair(s, e));
    nstack.push_back(NULL);
    
    while (! stack.empty())
    {
        itrPairPtr p = stack.back();
        stack.pop_back();
        node* anc = nstack.back();
        nstack.pop_back();
        
        if (p->first <= p->second)
        {
            constIntVectorItr m = mid(p->first, p->second);
            node* n = new node(*m);
            //cout << *m << endl;
            if (p->first == s && p->second == e)
            {
                root = n;
            }
            else
            {
                if (anc->val >= n->val && anc->left == NULL)
                {
                    anc->left = n;
                }
                else if (anc->val <= n->val && anc->right== NULL)
                {
                    anc->right = n;
                }
            }
            
            stack.push_back(new itrPair(p->first, m - 1));
            nstack.push_back(n);
            stack.push_back(new itrPair(m + 1, p->second));
            nstack.push_back(n);
        }
        delete p;
    }
    
    return root;
}

/*
This is better in logic
*/
node * Logic2_v2(const vector<int>& vec)
{
    if (vec.empty()) return NULL;
    
    typedef pair<const vector<int>::const_iterator, const vector<int>::const_iterator> mypair;
    
    const vector<int>::const_iterator s = vec.begin();
    const vector<int>::const_iterator e = vec.end() - 1;
    
    vector<mypair* > stack; //stack the ranges
    vector<node *> nstack; //stack the parent for a range
    
    stack.push_back(new mypair(s, e));
    const vector<int>::const_iterator m = mid(s, e);
    node* root = new node(*m);
    nstack.push_back(root);
    
    while (! stack.empty())
    {
        mypair* p = stack.back();
        stack.pop_back();
        node* anc = nstack.back();
        nstack.pop_back();
        
        if (p->first <= p->second)
        {
            const vector<int>::const_iterator m = mid(p->first, p->second);
            const vector<int>::const_iterator left  = mid(p->first, m - 1);
            const vector<int>::const_iterator right = mid(m + 1, p->second);
            if (left > m - 1)
            {
                anc->left = NULL;
            }
            else
            {
                node *ancleft = new node(*left);
                anc->left = ancleft;
                nstack.push_back(ancleft);
                stack.push_back(new mypair(p->first, m - 1));
            }
            if (right > p->second)
            {
                anc->right = NULL;
            }
            else
            {
                node *ancright = new node(*right);
                anc->right = ancright;
                nstack.push_back(ancright);
                stack.push_back(new mypair(m + 1, p->second));
            }      
        }
        delete p;
    }
    return root;
}

int main()
{
    int arr[10] = {0,1,2,3,4,5,6,7,8,9};
    intVector vec(arr, arr + 10);
    
    //node *root = Logic1(vec);
    //node *root = Logic2(vec);
    node *root = Logic2_v2(vec);
    
    //traverse and deconstruct
    node *n = NULL;
    nodePtrDeque queue;
    queue.push_back(root);
    /*
    set the NULL as level delimiter, made mistake here, be carefull about the logic
    */
    queue.push_back(NULL);
    while (! queue.empty())
    {
        n = queue.front();
        queue.pop_front();
        if (n == NULL)
        {
            cout << endl;
            if (! queue.empty())
                queue.push_back(NULL);
        }
        else
        {
            cout << n->val << ' ';
            if (n->left != NULL)
            {
                queue.push_back(n->left);
            }
            if (n->right != NULL)
            {
                queue.push_back(n->right);
            }
            delete n;
            n = NULL;
        }
    }
    return 0;
};