# DFS + iteration

• 1 DFS

``````class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
//insert from middle
return recursion(nums, 0, nums.size() - 1);
}

TreeNode* recursion(vector<int>& nums, int i, int j) {
if (i > j)
return NULL;
int mid = i + (j - i) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = recursion(nums, i, mid - 1);
root->right = recursion(nums, mid + 1, j);

return root;
}
};
``````

2 iteration

`````` struct Tree {
int low;
int high;
TreeNode * node;
Tree(int _low, int _high, TreeNode* _node) : low(_low), high(_high), node(_node) {}
};
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
if (nums.size() == 0)
return NULL;
int mid;
stack<Tree*> s;
TreeNode* root = new TreeNode(nums[(nums.size() - 1)/2]);
Tree* tree = new Tree(0, nums.size() - 1, root), *tmp = NULL;
s.push(tree);
while (!s.empty()) {
tmp = s.top();
s.pop();
mid = tmp->low + (tmp->high - tmp->low) / 2;
if (tmp->low < mid) {
TreeNode* node = new TreeNode(nums[tmp->low + (mid - 1 - tmp->low) / 2]);
tmp->node->left = node;
tree = new Tree(tmp->low, mid - 1, node);
s.push(tree);
}

if (mid < tmp->high) {
TreeNode* node = new TreeNode(nums[mid + 1 + (tmp->high - mid - 1)/2]);
tmp->node->right = node;
tree = new Tree(mid + 1, tmp->high, node);
s.push(tree);
}
}

return root;
}
};
``````

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