Sorted Array TO BST

108.Convert Sorted Array to Binary Search Tree

Tree

Binary Search Tree

Array

Divide and Conquer

Recursion

Problem Statement:

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

Example:

Input:

nums = [-10,-3,0,5,9]

→

Output:

[0,-3,9,-10,null,5]

Creates a balanced BST where middle element becomes root

Algorithm:

1. Use middle element as root to ensure balance
2. Recursively build left and right subtrees
3. Handle base cases (single element and empty range)
4. Return built tree back up recursion chain

Complexity:

Time: O(n) | Space: O(log n) recursive stack

Java Solution:

public TreeNode sortedArrayToBST(int[] nums) {
    return buildTree(nums, 0, nums.length - 1);
}

private TreeNode buildTree(int[] nums, int low, int high) {
    // Base case: single element
    if (low == high) 
        return new TreeNode(nums[low]);
        
    // Base case: invalid range
    if (low > high) 
        return null;
        
    // Find middle element for root
    int mid = low + (high - low) / 2;
    TreeNode node = new TreeNode(nums[mid]);
    
    // Recursively build left and right subtrees
    node.left = buildTree(nums, low, mid - 1);
    node.right = buildTree(nums, mid + 1, high);
    
    return node;
}

Python Solution:

def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
    def buildTree(low: int, high: int) -> Optional[TreeNode]:
        # Base case: single element
        if low == high:
            return TreeNode(nums[low])
            
        # Base case: invalid range
        if low > high:
            return None
            
        # Find middle element for root
        mid = low + (high - low) // 2
        node = TreeNode(nums[mid])
        
        # Recursively build left and right subtrees
        node.left = buildTree(low, mid - 1)
        node.right = buildTree(mid + 1, high)
        
        return node
        
    return buildTree(0, len(nums) - 1)

C++ Solution:

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return buildTree(nums, 0, nums.size() - 1);
    }
    
private:
    TreeNode* buildTree(vector<int>& nums, int low, int high) {
        // Base case: single element
        if (low == high)
            return new TreeNode(nums[low]);
            
        // Base case: invalid range
        if (low > high)
            return nullptr;
            
        // Find middle element for root
        int mid = low + (high - low) / 2;
        TreeNode* node = new TreeNode(nums[mid]);
        
        // Recursively build left and right subtrees
        node->left = buildTree(nums, low, mid - 1);
        node->right = buildTree(nums, mid + 1, high);
        
        return node;
    }
};