108. Convert Sorted Array to Binary Search Tree

# Easy

Finding medium of a sorted list to be root and add to root.left and root.right respectively. Use recursive.

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

Second Tab

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