# Is there any good iterative O(1) space solution out there?

• I understand that this problem can be most naturally solved with recursion. However, I wonder if there is an iterative solution that only uses constant space (aside from the space occupied by the input array and the output tree nodes). For now, the only thing I can think of is Morris Traversal, but I wonder if a simpler solution exists for this particular problem. Any suggestion would be appreciated!

• How do you like this? It's a recursive way, but it doesn't require copy stuff around but just constructs the tree based on given num. I LOVE Python. =)

``````class Solution:
# @param num, a list of integers
# @return a tree node
def sortedArrayToBST(self, num):

def convert_array(left, right):
"""Convert num[left:right] to a (sub)tree."""

# num[x:x] is an empty list (x is any number)
if left >= right:
return None

# mid point at the very middle of num[left:right]
# or the right one of the middle two
mid = (left + right) / 2

root = TreeNode(num[mid])
root.left = convert_array(left, mid)
root.right = convert_array(mid + 1, right)

return root

return convert_array(0, len(num))``````

• While this solution works great on my local machine, OJ is spitting run time error.

• It passed OJ before. I'd guess they might add a test case where `num` is None, and `len(None)` would raise `TypeError`.

• Isn't this a recursive solution? Somebody help me out here?

• Build the complete binary tree structure first, then use standard Morris traverse to assign value on each node.

``````public TreeNode sortedArrayToBST(int[] nums) {
int len = nums.length;
if(len==0){
return null;
}

TreeNode root = new TreeNode(0);
len--;

int layer = 1;
while(len>0){
layer *= 2;
for(int i=0;i<layer&&len>0;i++,len-=2){
TreeNode cur = q.poll();
cur.left = new TreeNode(0);
if(len>1){
cur.right = new TreeNode(0);
}
}
}

int i=0;
TreeNode cur = root;
while(cur!=null){
if(cur.left==null){
cur.val = nums[i++];
cur = cur.right;
}else {
TreeNode pre = cur.left;
while(pre.right!=null && pre.right!=cur){
pre = pre.right;
}

if(pre.right==null){
pre.right = cur;
cur = cur.left;
}else {
pre.right = null;

// pre must has a value now
cur.val = nums[i++];
cur = cur.right;
}
}
}

return root;
}
``````

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