# Iterative Java Solution Using Stack

• Try to solve it iteratively, need an extra class to store:

1. current TreeNode's coverage [low, up]

2. current TreeNode entity

()

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

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