# Accepted C++ recursive solution within a single method

• Recursively call the sortedArrayToBST() method providing new vector for each call to construct left and right children:

``````class Solution {
public:
TreeNode *sortedArrayToBST(vector<int> &num) {
if(num.size() == 0) return NULL;
if(num.size() == 1)
{
return new TreeNode(num[0]);
}

int middle = num.size()/2;
TreeNode* root = new TreeNode(num[middle]);

vector<int> leftInts(num.begin(), num.begin()+middle);
vector<int> rightInts(num.begin()+middle+1, num.end());

root->left = sortedArrayToBST(leftInts);
root->right = sortedArrayToBST(rightInts);

return root;
}
};``````

• ``````if(num.size() == 1)
{
return new TreeNode(num[0]);
}
``````

The above part is redundant. Nevertheless, your code is still concise and inspiring.

• Why don't you have a helper function and pass lo,hi instead of passing new vectors in each and every call?

• A more efficient and concise implementation

`````` class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return help(nums, 0, nums.size()-1);
}

TreeNode* help(vector<int> &nums, int start, int end){
int _size=end-start;
if(_size<0)    return NULL;
if(_size==0)    return new TreeNode(nums[start]);
int mid=(start+end)/2;
TreeNode* root=new TreeNode(nums[mid]);
root->left=help(nums, start, mid-1);
root->right=help(nums, mid+1, end);
}
};``````

• @sudeep3
Are you asking this because you don't know or because you want him to use the helper method approach ?

• Very fun alternative but this uses the copy constructor which kills performance for arrays of any large length.

• How come your help function does not always return a value?
your return value only exist in if statement. the leaf node will return for sure, but the parent node may not?
But anyway, if I add a return at the end like "return root;", it does not make difference

• I think because it is a recursive solution, keep new new objects might incur more memory consumption than just using begin and end index of the array. In the worst case, the memory will run out.

• Time complexity of your algorithm is O(nlogn) because of the copy. Following is the amount of the copy. And it also requires O(nlogn) space. I think this is not a considerable solution because
the simple recursion with the indexes runs in O(n) time and O(logn) space.

``````# When n = 16
L1               8 8
L2             4 4 4 4
L3         2 2 2 2 2 2 2 2
L4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
`````````

• The special case doesn't need
if(num.size() == 1)
{
return new TreeNode(num[0]);
}

• It is better to use iterator instead of index when dealing with c++ std library.

``````class Solution {
public:
using iter = vector<int>::const_iterator;
TreeNode* sortedArrayToBST(vector<int>& nums) {
if (nums.empty()) return nullptr;

return buildBST(nums.begin(), nums.end());
}

TreeNode* buildBST(iter b, iter e) {
if (b >= e) return nullptr;

iter m = b + (e - b) / 2;

TreeNode* node = new TreeNode(*m);
node->left = buildBST(b, m);
node->right = buildBST(m + 1, e);

return node;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.