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