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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Convert Sorted Array to Binary Search Tree

Difficulty: Easy

Problem Description

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

Key Insights

  • A height-balanced binary search tree is defined such that the depth of the two subtrees of every node never differs by more than one.
  • The middle element of the sorted array should be chosen as the root to ensure balance.
  • The left subarray forms the left subtree, and the right subarray forms the right subtree.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we use a recursive approach. The algorithm follows these steps:

  1. If the input array is empty, return null.
  2. Find the middle index of the array (this will be the root of the current subtree).
  3. Create a new tree node with the middle element.
  4. Recursively build the left subtree using the left half of the array and the right subtree using the right half of the array.
  5. Return the root node.

The data structure used is a binary tree node, and the algorithm is based on the divide and conquer approach, ensuring that each subtree remains balanced.

Code Solutions

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def sortedArrayToBST(nums):
    if not nums:
        return None
    mid = len(nums) // 2  # Find the middle index
    root = TreeNode(nums[mid])  # Create the root node
    root.left = sortedArrayToBST(nums[:mid])  # Recursively build the left subtree
    root.right = sortedArrayToBST(nums[mid + 1:])  # Recursively build the right subtree
    return root
← Back to All Questions