---
tags: data_structure_python
---

# Convert Sorted Array to Binary Search Tree <img src="https://img.shields.io/badge/-easy-brightgreen">

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

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

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

<ins>**Example:**</ins>

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

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

## Solution

# 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]) -> Optional[TreeNode]:
        
        mid = int(len(nums) / 2)
        
        root = TreeNode(nums[mid])
        
        if mid - 1 >= 0:
            root.left = self.sortedArrayToBST(nums[:mid])
        if mid + 1 < len(nums):
            root.right = self.sortedArrayToBST(nums[mid + 1:])
        
        return root

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def __sortedArrayToBST(self, nums, l, r):
        if l > r:
            return None
        else:
            mid = l + (r-l)//2 
            root = TreeNode(nums[mid])
        
            # divide
            root.left = self.__sortedArrayToBST(nums, l, mid-1)
            root.right = self.__sortedArrayToBST(nums, mid+1, r)

            return root
    
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        return self.__sortedArrayToBST(nums, 0, len(nums)-1)