108. Convert Sorted Array to Binary Search Tree

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

Solution: DFS

class Solution(object):
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """

        def dfs(low, high):
            if low > high:
                return None
            mid = low + (high - low) / 2
            root = TreeNode(nums[mid])
            root.left = dfs(low, mid - 1)
            root.right = dfs(mid + 1, high)
            return root

        return dfs(0, len(nums) - 1)

Related:

• 109. Convert Sorted List to Binary Search Tree