# Java Iterative Solution

• 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

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);
}
}
}

}``````

• Great idea. The recursion approach is quite boring and let me share my iterative solution using BFS. There is a queue under the hood. And also a small data type encapsulate necessary info. Briefly, we assemble the tree from upper level to lower level, from left sibling to rightmost sibling. I think it is straight forward.

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

int left = 0;
int right = nums.length - 1;
int val = nums[left + (right - left) / 2];
TreeNode root = new TreeNode(val);
queue.offer(new MyNode(root, left, right));

while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
MyNode cur = queue.poll();

int mid = cur.lb + (cur.rb - cur.lb) / 2;

if (mid != cur.lb) {
TreeNode leftChild = new TreeNode(nums[cur.lb + (mid - 1 - cur.lb) / 2]);
cur.node.left = leftChild;
queue.offer(new MyNode(leftChild, cur.lb, mid - 1));
}

if (mid != cur.rb) {
TreeNode rightChild = new TreeNode(nums[mid + 1 + (cur.rb - mid - 1) / 2]);
cur.node.right = rightChild;
queue.offer(new MyNode(rightChild, mid + 1, cur.rb));
}
}
}

return root;
}

private static class MyNode {
TreeNode node;
int lb;
int index;
int rb;

public MyNode(TreeNode n, int theLeft, int theRight) {
this.node = n;
this.lb = theLeft;
this.rb = theRight;
}
}
}
``````

• ``````public class MyNode{
TreeNode node;
int start;
int end;

public MyNode(int start, int end, TreeNode node){
this.start = start;
this.end = end;
this.node = node;
}
}

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

Stack<MyNode> stack = new Stack<MyNode>();
int mid = 0 + (nums.length -1 - 0)/2;
TreeNode root = new TreeNode(nums[mid]);
MyNode MyRoot = new MyNode(0, nums.length -1, root);
stack.push(MyRoot);
while(!stack.isEmpty()){
MyNode curr = stack.pop();
int oldMid = curr.start + (curr.end - curr.start)/2;
if(oldMid -1 >= curr.start){
mid = curr.start + (oldMid-1 - curr.start)/2;
root = new TreeNode(nums[mid]);
stack.push(new MyNode(curr.start, oldMid - 1, root));
curr.node.left = root;
}

if(oldMid +1 <= curr.end){
mid = oldMid +1 + (curr.end - oldMid -1)/2;
root = new TreeNode(nums[mid]);
stack.push(new MyNode(oldMid + 1, curr.end, root));
curr.node.right = root;
}
}

return MyRoot.node;
}
``````

Use an inner class to save space

• You are actually doing a preorder traversal...

• @Adeath It's good to find someone who sees the same problem :) In this case any traversal used could solve the problem though.

• instead of using two index stack, or wrap them up in a wrapper class, could just merge them into one stack.

• @516364598chang Great solution. I'd argue that you don't even need the following lines inside the queue while :

``````int size = queue.size();
for (int i = 0; i < size; i++) {
...
}
``````

The queue will pop all the nodes even without that loop and the function works fine.

• beats 0.94% why?
slower than recursion

• your program seems like dfs, but use same space as bfs, maybe we can reduce the use of space.

• Use a private class to make it more readable

``````	private class Node {
TreeNode node;
int left, right;
public Node(TreeNode node, int left, int right) {
this.node = node;
this.left = left;
this.right = right;
}
}
public TreeNode sortedArrayToBST(int[] nums) {
if (nums == null || nums.length == 0) return null;
TreeNode root = new TreeNode(0);
Stack<Node> stack = new Stack<>();
Node node = new Node(root, 0, nums.length - 1);
stack.push(node);
while (!stack.isEmpty()) {
Node cur = stack.pop();
int mid = cur.left + (cur.right - cur.left) / 2;
cur.node.val = nums[mid];
if (cur.left < mid) {
cur.left = new TreeNode(0);
stack.push(new Node(cur.left, cur.left, mid - 1));
}
if (cur.right > mid) {
cur.right = new TreeNode(0);
stack.push(new Node(cur.right, mid + 1, cur.right));
}
}
return root;
}

``````

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