# 108 Convert Sorted Array to Binary Search Tree

## 108. Convert Sorted Array to Binary Search Tree

## 1. Question

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

## 2. Implementation

**(1) Recursion**

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

        return generateBST(nums, 0, nums.length - 1);
    }

    public TreeNode generateBST(int[] nums, int start, int end) {
        if (start > end) {
            return null;
        }

        int mid = start + (end - start) / 2;
        TreeNode curNode = new TreeNode(nums[mid]);
        curNode.left = generateBST(nums, start, mid - 1);
        curNode.right = generateBST(nums, mid + 1, end);
        return curNode;
    }
}
```

**(2) Iterative**

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

        TreeNode root = new TreeNode(0);
        Stack<TreeNode> nodes = new Stack<>();
        Stack<Integer> leftIndexes = new Stack<>();
        Stack<Integer> rightIndexes = new Stack<>();

        nodes.push(root);
        leftIndexes.push(0);
        rightIndexes.push(nums.length - 1);

        while (!nodes.isEmpty()) {
            TreeNode curNode = nodes.pop();
            int start = leftIndexes.pop();
            int end = rightIndexes.pop();

            int mid = start + (end - start) / 2;
            curNode.val = nums[mid];

            if (start <= mid - 1) {
                curNode.left = new TreeNode(0);
                nodes.push(curNode.left);
                leftIndexes.push(start);
                rightIndexes.push(mid - 1);
            }

            if (end >= mid + 1) {
                curNode.right = new TreeNode(0);
                nodes.push(curNode.right);
                leftIndexes.push(mid + 1);
                rightIndexes.push(end);
            }
        }
        return root;
    }
}
```

## 3. Time & Space Complexity

Recursion: 时间复杂度O(n), 空间复杂度: O(logn)

Iteration: 时间复杂度O(n), 空间复杂度: O(n)
