> For the complete documentation index, see [llms.txt](https://r24zeng.gitbook.io/leetcode-notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://r24zeng.gitbook.io/leetcode-notebook/binary-search-and-tree/108.-convert-sorted-array-to-binary-search-tree.md).

# 108. Convert Sorted Array to Binary Search Tree

\# Easy

{% hint style="info" %}
Finding medium of a sorted list to be root and add to `root.left` and `root.right` respectively. Use recursive.
{% endhint %}

{% tabs %}
{% tab title="Python" %}

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        # edge case
        if len(nums) == 0:
            return None
        
        root = TreeNode(nums[0])
        if len(nums) == 1:
            return root
        
        # regular case
        root.val = nums[len(nums)//2]
        root.left = self.sortedArrayToBST(nums[:len(nums)//2])
        root.right = self.sortedArrayToBST(nums[len(nums)//2+1:])
        
        return root
```

{% endtab %}

{% tab title="Second Tab" %}

{% endtab %}
{% endtabs %}

Time complexity = $$O(n)$$ , space complexity = $$O(1)$$ because only need to record the root.