083.md

108. Convert Sorted Array to Binary Search Tree**

Difficulty: 🟢 Easy

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

Examples:

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:

Example 2:

Input: nums = [1,3]
Output: [3,1]
Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.

Constraints:

• 1 <= nums.length <= 104
• 104 <= nums[i] <= 104
• nums is sorted in a strictly increasing order.

Solutions

O(n) solution

Python3

# 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 build_tree(nums, low, high):
            if low == high:
                return None

            mid = (low + high) // 2
            node = TreeNode(nums[mid])
            node.left = build_tree(nums, low, mid) 
            node.right = build_tree(nums, mid+1, high)
            return node

        return build_tree(nums, 0, len(nums))

The given solution provides a recursive approach to convert a sorted integer array into a height-balanced binary search tree.

Here is a step-by-step overview of the solution:

1. Define a recursive function build_tree that takes the array nums, and the lower and upper indices (low and high) as arguments.
2. If the lower index is equal to the upper index, return None as there is no node to create.
3. Calculate the middle index as (low + high) // 2.
4. Create a new node with the value at the middle index in the nums array.
5. Recursively call the build_tree function for the left half of the array (from low to mid).
6. Recursively call the build_tree function for the right half of the array (from mid+1 to high).
7. Assign the left and right subtrees obtained from the recursive calls to the left and right children of the current node.
8. Return the current node.

Finally, call the build_tree function with appropriate arguments to construct the height-balanced binary search tree.

Complexity Analysis

The time complexity for this solution is O(n), where n is the number of elements in the input array nums. This is because we are visiting each element once.

The space complexity is O(log n) due to the recursion stack. In the worst case, the recursion depth can go up to log n levels.

Summary

The given solution provides a recursive approach to convert a sorted integer array into a height-balanced binary search tree. It recursively divides the array into halves and constructs the tree nodes accordingly. The solution has a time complexity of O(n) and a space complexity of O(log n), where n is the number of elements in the input array.

NB: If you want to get community points please suggest solutions in other languages as merge requests.