108. Convert Sorted Array to Binary Search Tree

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
• topics: Tree

Given an integer array nums where the elements are sorted in ascending order, convert it to a 

height-balanced

 binary search tree.

# 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]:
        def bst(left, right):
            center = (left + right) // 2
            node = TreeNode(nums[center])
            if center == left + 1:
                node.left = TreeNode(nums[left])
            elif center > left:
                node.left = bst(left, center-1)
            if center == right - 1:
                node.right = TreeNode(nums[right])
            elif center < right:
                node.right = bst(center+1, right)  
            return node
        return bst(0, len(nums)-1)