Convert Sorted Array to Binary Search Tree

Problem Id: 108 Difficulty: Easy Tag: Tree Tag: Depth-first Search


Given a sorted array, the middle value could be used as the root value of the binary search tree. And its left could be used to construct the left subtree. The right subtree is also like this.


# 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: List[int]) -> TreeNode:
        return self._helper(nums, 0, len(nums))

    def _helper(self, nums, lo, hi):
        if lo == hi:
            return None
        mid = (lo + hi) // 2
        node = TreeNode(nums[mid])
        node.left = self._helper(nums, lo, mid)
        node.right = self._helper(nums, mid + 1, hi)
        return node