We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Convert Sorted Array to Binary Search Tree

Number: 108

Difficulty: Easy

Paid? No

Companies: Google, Amazon, Bloomberg, Microsoft, Apple, Airbnb

Problem Description

Given an integer array nums sorted in ascending order, convert it to a height-balanced binary search tree. A height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differs by more than 1.

Key Insights

  • The array is sorted in ascending order, which allows the use of a divide and conquer strategy.
  • Choosing the middle element of the array as the root ensures that the left and right subtrees are roughly equal in size, yielding a balanced BST.
  • A recursive approach is natural for building the tree: the base case is when the subarray is empty.
  • The algorithm splits the array into two halves to recursively build the left and right subtrees.

Space and Time Complexity

Time Complexity: O(n) - Every element is processed exactly once. Space Complexity: O(n) - O(n) space is used to store the BST, and additional O(log n) space may be used for the recursion stack.

Solution

We use a divide and conquer approach with recursion. The main idea is to select the middle element of the current subarray as the root node so that the left subarray elements form the left subtree and the right subarray elements form the right subtree, ensuring the tree is balanced. The recursion continues until the subarray is empty, which serves as the base case. This strategy naturally maintains the BST property since all elements in the left subarray are smaller than the root, and all in the right subarray are larger.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    # Initializes a tree node with a value and optional left/right children.
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def sortedArrayToBST(self, nums):
        # Helper function to build BST from subarray indices.
        def buildBST(left, right):
            # Base condition: if no elements to process, return None.
            if left > right:
                return None
            # Choose the middle element as the root for balance.
            mid = (left + right) // 2
            node = TreeNode(nums[mid])
            # Recursively build the left subtree.
            node.left = buildBST(left, mid - 1)
            # Recursively build the right subtree.
            node.right = buildBST(mid + 1, right)
            return node
        # Build and return the BST from the entire array.
        return buildBST(0, len(nums) - 1)
← Back to All Questions