Convert Sorted Array to Binary Search Tree

Convert Sorted Array to Binary Search Tree
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

-------------------------------- thinking ------------------------------------------------------
recursive is the easiest way to go
read codes for iterative way!!!!!!!!!!!!!!!!!!!!!!

----------------------------------- codes ------------------------------------------------------
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *sortedArrayToBST(vector<int> &num) {
        if (num.size() == 0) {
            return NULL;
        }
        return convertHelper(num, 0, num.size() - 1);
    }
    TreeNode *convertHelper(vector<int> &num, int i, int j) {
        if (i == j) {
            TreeNode *ele = new TreeNode(num[i]);
            return ele;
        }
        if (i + 1 == j) {
            TreeNode *ele = new TreeNode(num[i]);
            TreeNode *ele_right = new TreeNode(num[j]);
            ele->right = ele_right;
            return ele;
        }
        int medium = i + (j - i) / 2;
        TreeNode *ele = new TreeNode(num[medium]);
        TreeNode *ele_left = NULL;
        TreeNode *ele_right = NULL;
        if (i <= medium - 1) {
            ele_left = convertHelper(num, i, medium - 1);
        }
        if (medium + 1 <= j) {
            ele_right = convertHelper(num, medium + 1, j);
        }
        ele->left = ele_left;
        ele->right = ele_right;
        return ele;
    }
};
----------------------------- read codes ------------------------------------------------------------
https://oj.leetcode.com/discuss/10746/there-anybody-can-solve-this-problem-without-using-recursion
public TreeNode sortedArrayToBST(int[] num) { Queue<TreeNode> nodes = new LinkedList<TreeNode>(); int length = num.length, i = 1 , c = 4, l = 0, r = 0, s = 1; int[] trace = new int[length]; if (length == 0) { return null; } TreeNode root = new TreeNode(num[length/2]); nodes.add(root); //trace is to track if an element in num has been added to tree trace[length/2] = 1; while (s != length) { while (i < c) { TreeNode n = nodes.poll(); if (n != null) { // i / c = 1/4, 1/8, 5/8 ... l = (i*length)/c; // (i+2) / c = 3/4, 3/8, 7/8... r = (i+2)*length/c; TreeNode left = null, right = null; if (trace[l] != 1) { s++; trace[l] = 1; left = new TreeNode(num[l]); } if (trace[r] != 1) { s++; trace[r] = 1; right = new TreeNode(num[r]); } n.left = left; n.right = right; nodes.add(left); nodes.add(right); } i += 4; } i = 1; c *= 2; } return root; }