Convert Sorted Array to Binary Search Tree

Problem: LeetCode 108
Difficulty: Easy
Topic: Binary Tree, Divide and Conquer, Recursion

Problem Summary#

Given a sorted array nums in ascending order, convert it into a height-balanced BST — one where the depth of the two subtrees of every node never differs by more than 1.

Approach: Divide and Conquer (Pick Middle as Root)#

Intuition: In a BST, the root determines what goes left and right. To keep the tree balanced, the root should split the remaining elements as evenly as possible — so always pick the middle element as the root. Recurse on the left half for the left subtree and the right half for the right subtree.

The array being sorted already satisfies the BST property: everything left of mid is smaller, everything right is larger.

The function uses a half-open interval [start, end) — end is exclusive, matching nums.size() as the initial call.

class Solution {
public:
    TreeNode* createBST(vector<int>& nums, int start, int end) {
        if (start >= end)       // empty interval
            return NULL;

        int midIdx = (start + end) / 2;

        TreeNode* root = new TreeNode(nums[midIdx]);

        root->left  = createBST(nums, start, midIdx);      // left half
        root->right = createBST(nums, midIdx + 1, end);    // right half

        return root;
    }

    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return createBST(nums, 0, nums.size());
    }
};

Complexity#

Notes#

• Picking mid = (start + end) / 2 biases toward the left-center on even-length arrays — this is valid. Picking mid = (start + end + 1) / 2 (right-center) is equally valid; both produce a height-balanced BST, just slightly different shapes.
• The base case start >= end handles both the empty array and the case where a subarray has been fully consumed.
• Multiple valid answers exist — LeetCode accepts any height-balanced BST that satisfies the inorder traversal.