108. Convert Sorted Array to Binary Search Tree

Problem¶

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

Example 1:

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

Solve¶

O(n)

A simple recursion, we reuse our own created function
Recursion break case is when:

len(nums) == 0 which we return None
len(nums)== 1 which it is a leaf TreeNode with leaf.left = leaf.right == None

# 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]:
        if len(nums) == 1:
            return TreeNode(nums[0])

        if len(nums) ==0:
            return None

        mid = len(nums)//2
        root_value = nums[mid]
        left = self.sortedArrayToBST(nums[:mid])
        right = self.sortedArrayToBST(nums[mid+1:])

        return TreeNode(root_value, left, right)

Last update : September 17, 2023
Created : August 16, 2023