# Is there anybody can solve this problem without using recursion?

• Is there anybody can solve this problem without using recursion?And what is the time & space complexity?

• ``````public TreeNode sortedArrayToBST(int[] num) {
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]);

//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;
}
i += 4;
}
i = 1;
c *= 2;
}
return root;
}``````

• There is always a way to convert recursion to iterative. I have tried to use a queue and it seems working.
Worst time: O(n), worst space O(n).

``````private class NodeE extends TreeNode {
int i = 0;         //corresponding num index
int iL = 0;        //left index of un-searched
int iR = 0;        //right index of un-searched
NodeE(int val, int i, int iL, int iR) {
super(val);
this.i = i;
this.iL = iL;
this.iR = iR;
}
}

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

Deque<NodeE> q = new ArrayDeque<NodeE>();
NodeE root = new NodeE(num[num.length / 2], num.length/2, 0, num.length - 1);

while (!q.isEmpty()) {
NodeE n = q.remove();
if (n.i > n.iL) { // left half, from iL to i - 1!
int nextI = (n.iL + n.i) / 2;
NodeE nL = new NodeE(num[nextI], nextI, n.iL, n.i -1);
n.left = nL;
}
if (n.i < n.iR) { // right half, from i + 1 to iR!
int nextI = (n.i + 1 + n.iR + 1) / 2;
NodeE nR = new NodeE(num[nextI], nextI, n.i + 1, n.iR);
n.right = nR;
}
}
return root;
}``````

• The i/c sequence is ingenious! @bravejia you have truly mastered math skills.

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