# Yet another iterative solution C++ O(n)

• `````` struct Data
{
TreeNode *node;
int l;
int r;
Data(int iL, int iR, vector<int> &num)
{
l = iL;
r = iR;
node = NULL;

if (l>=r) return ;

int mid = l + (r-l)/2;
node = new TreeNode(num[mid]);
}
};

class Solution {
public:

TreeNode *sortedArrayToBST(vector<int> &num) {
stack<Data> s;

Data root(0, num.size(), num);
s.push(root);

while (!s.empty())
{
Data pop = s.top(); s.pop();

if (!pop.node) continue;

int mid = pop.l + (pop.r - pop.l)/2;

Data left(pop.l, mid, num);
Data right(mid+1, pop.r, num);

pop.node->left = left.node;
pop.node->right = right.node;

s.push(left);
s.push(right);
}

return root.node;
}
};``````

• A slight modification on this approach

`````` struct Node{
TreeNode* t;
int l;
int r;
Node(vector<int> &num, int l, int r){
this->t = new TreeNode(num[l+(r-l)/2]);
this->l = l;
this->r = r;
}

Node* getLeft(vector<int> &num){
int m = l + (r-l)/2;
if(l>=m) return NULL;
Node* left = new Node(num, l, m);
t->left = left->t;
return left;
}

Node* getRight(vector<int> &num){
int m = l + (r-l)/2;
if(m+1>=r) return NULL;
Node* right = new Node(num, m+1, r);
t->right = right->t;
return right;
}
};

class Solution {
public:

TreeNode *sortedArrayToBST(vector<int> &num) {
if(num.size()==0) return NULL;
stack<Node*> s;
Node* root = new Node(num, 0, num.size());
s.push(root);
while(!s.empty()){
Node* n = s.top(); s.pop();

Node* left = n->getLeft(num);
if(left) s.push(left);

Node* right = n->getRight(num);
if(right) s.push(right);
}
return root->t;
}
};``````

• Similar approach in Java

``````public class Solution {
public TreeNode sortedArrayToBST(int[] num) {
if(num.length == 0) return null;

Stack<ArrayNode> stack = new Stack<ArrayNode>();
int middle ;
ArrayNode aroot = new ArrayNode(num, 0, num.length-1);
TreeNode root = aroot.r;
stack.push(aroot);

while(!stack.empty()){
ArrayNode n = stack.pop();
middle = n.left + (n.right-n.left)/2;
if(n.right > middle) {
ArrayNode rightN = new ArrayNode(num, middle+1, n.right);
n.r.right = rightN.r;
stack.push(rightN);
}
if(n.left < middle){
ArrayNode leftN = new ArrayNode(num, n.left, middle-1);
n.r.left = leftN.r;
stack.push(leftN);
}
}
return root;
}

private class ArrayNode {
TreeNode r;
int left;
int right;
public ArrayNode(int[] num, int left, int right){
r = new TreeNode(num[left + (right-left)/2]); //check
this.left = left;
this.right = right;
}
}
}``````

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