 # Can we solve this problem in iterative way?

#1

I have solved this question using recursion. But I am curious to know that whether it is possible to solve without recursion ?
Any suggestion will be welcome.
Thanks.

#2

Check out my code:
What I did is first created empty tree iteratively and did inorder traversal to populate the empty BST.
You can implement inorder traversal iteratively also but it will make code lengthier.

``````TreeNode* node(){
// helper function to get an empty node
TreeNode* temp = (TreeNode*)malloc(sizeof(TreeNode));
temp->left=NULL;
temp->right= NULL;
return temp;
}
TreeNode * createtree(int n){
//Create an empty balanced BST with given number of nodes by level order traversal s.t
//level balanced is maintained
queue<TreeNode*> q;
n--;
while(1){
TreeNode * temp = q.front();
q.pop();
if(n){
TreeNode * lefty = node();
temp->left = lefty;
n--;
q.push(lefty);
}
else break;
if(n){
TreeNode * righty = node();
temp->right = righty;
n--;
q.push(righty);
}
else break;
}
}
void populate(TreeNode * root, const vector<int > &v, int * i){
//Inorder traversal and populating empty balanced BST
if(!root)
return;
populate(root->left, v,i);
root->val = v[*i];
*i = *i +1;
populate(root->right, v, i);
}
TreeNode* Solution::sortedArrayToBST(const vector<int> &A) {
//Driver function
int n= A.size();
int i=0;
TreeNode* root = createtree(n);
populate(root, A, &i);
return root;
}``````