I came up with the recursion solution first and tried to translate it into an iterative solution. It is very similar to doing a tree inorder traversal, I use three stacks - nodeStack stores the node I am going to process next, and **leftIndexStack** and **rightIndexStack** store the range where this node need to read from the **nums**.

```
public class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
int len = nums.length;
if ( len == 0 ) { return null; }
// 0 as a placeholder
TreeNode head = new TreeNode(0);
Deque<TreeNode> nodeStack = new LinkedList<TreeNode>() {{ push(head); }};
Deque<Integer> leftIndexStack = new LinkedList<Integer>() {{ push(0); }};
Deque<Integer> rightIndexStack = new LinkedList<Integer>() {{ push(len-1); }};
while ( !nodeStack.isEmpty() ) {
TreeNode currNode = nodeStack.pop();
int left = leftIndexStack.pop();
int right = rightIndexStack.pop();
int mid = left + (right-left)/2; // avoid overflow
currNode.val = nums[mid];
if ( left <= mid-1 ) {
currNode.left = new TreeNode(0);
nodeStack.push(currNode.left);
leftIndexStack.push(left);
rightIndexStack.push(mid-1);
}
if ( mid+1 <= right ) {
currNode.right = new TreeNode(0);
nodeStack.push(currNode.right);
leftIndexStack.push(mid+1);
rightIndexStack.push(right);
}
}
return head;
}
}
```