Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

Naive Way: A recursive method just came to my mind. Keep finding the middle element as root and recursive on both half.

 /**  
  * Definition for binary tree  
  * public class TreeNode {  
  *   int val;  
  *   TreeNode left;  
  *   TreeNode right;  
  *   TreeNode(int x) { val = x; }  
  * }  
  */  
 public class Solution {  
   public TreeNode sortedArrayToBST(int[] num) {  
     return sortedArrayToBST(num, 0, num.length-1);  
   }  
   public TreeNode sortedArrayToBST(int[] num, int begin, int end){  
     // base case  
     if(begin > end) return null;  
     // recursion  
     int middle = (begin+end)/2;  
     TreeNode root = new TreeNode(num[middle]);  
     root.left = sortedArrayToBST(num, begin, middle-1);  
     root.right = sortedArrayToBST(num, middle+1, end);  
     return root;  
   }  
 }  

Improved Way: As long as there is a recursive method, there is a corresponding iterative method. Let me try to solve it iteratively.

I cannot implement it without using another class to store multi-informaiton. Each time stack pops, I need to access lower bound, upper bound, and current TreeNode.

 /**  
  * Definition for binary tree  
  * public class TreeNode {  
  *   int val;  
  *   TreeNode left;  
  *   TreeNode right;  
  *   TreeNode(int x) { val = x; }  
  * }  
  */  
 public class Solution {  
   class Node{ // need another class to store multi information  
     int low, up; // means the TreeNode covers [low, up], low and up are all index  
     TreeNode t;  
     Node(int l, int p, TreeNode node){  
       low = l;  
       up = p;  
       t = node;  
     }  
   }  
   public TreeNode sortedArrayToBST(int[] num) {  
     if(num == null || num.length == 0) return null;  
     Stack<Node> stack = new Stack<Node>();  
     // initialize  
     TreeNode root = new TreeNode(num[(num.length-1)/2]);  
     Node rootNode = new Node(0,num.length-1,root);  
     stack.push(rootNode);  
     // iteration  
     while(!stack.isEmpty()){  
       Node node = stack.pop();  
       int middle = (node.low+node.up)/2; // cut half for [low, up]  
       // [low, middle-1]  
       if(middle-1 >= node.low){  
         TreeNode leftnode = new TreeNode(num[(middle-1+node.low)/2]);  
         node.t.left = leftnode;  
         Node left = new Node(node.low, middle-1, leftnode);  
         stack.push(left);  
       }  
       // [middle+1, up]  
       if(middle+1 <= node.up){  
         TreeNode rightnode = new TreeNode(num[(middle+1+node.up)/2]);  
         node.t.right = rightnode;  
         Node right = new Node(middle+1, node.up, rightnode);  
         stack.push(right);  
       }  
     }  
     return root;  
   }  
 }