> For the complete documentation index, see [llms.txt](https://zhongquan789.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zhongquan789.gitbook.io/leetcode/lcci/mian-shi-ti-04.02.md).

# 面试题 04.02

Given a sorted (increasing order) array with unique integer elements, write an algo­rithm to create a binary search tree with minimal height.

Example:

Given sorted array: \[-10,-3,0,5,9],

One possible answer is: \[0,-3,9,-10,null,5]，which represents the following tree:

```
      0 
     / \ 
   -3   9 
   /   / 
 -10  5 
```

## Solutions

1. **binary search tree**
2. Recursively build the root node with the middle element and link subtrees of two parts as the child nodes.

```cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode * create_bst(vector<int> & nums, int lo, int hi) {
        if (lo >= hi) return nullptr;
        else if (hi - lo == 1)
            return new TreeNode(nums[lo]);
        else {
            int mid = lo + ((hi - lo) >> 1);
            TreeNode * root = new TreeNode(nums[mid]);
            root->left = create_bst(nums, lo, mid);
            root->right = create_bst(nums, mid + 1, hi);
            return root;
        }
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return create_bst(nums, 0, nums.size());
    }
};
```