Build a Balanced BST From a Sorted Array

easy tree bst divide and conquer

Problem

Given an integer array sorted in ascending order, build a height-balanced binary search tree.

Recurse over [lo, hi]. Pick mid = (lo + hi) / 2 as the subtree root, recurse on [lo, mid - 1] for the left subtree, and [mid + 1, hi] for the right. The number of elements on either side of mid differs by at most one, so every subtree is balanced by construction.

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

Outputtree rooted at 0 with children -10/-3 left, 5/9 right

Mid index 2 → 0 root; left half [-10, -3] → -3 root; right half [5, 9] → 9 root.

sorted nums (comma-separated)

def sorted_to_bst(nums):
    def build(lo, hi):
        if lo > hi: return None
        mid = (lo + hi) // 2
        node = TreeNode(nums[mid])
        node.left = build(lo, mid - 1)
        node.right = build(mid + 1, hi)
        return node
    return build(0, len(nums) - 1)

function sortedToBST(nums) {
  function build(lo, hi) {
    if (lo > hi) return null;
    const mid = (lo + hi) >> 1;
    const node = { val: nums[mid], left: null, right: null };
    node.left = build(lo, mid - 1);
    node.right = build(mid + 1, hi);
    return node;
  }
  return build(0, nums.length - 1);
}

public TreeNode sortedToBST(int[] nums) {
    return build(nums, 0, nums.length - 1);
}
TreeNode build(int[] a, int lo, int hi) {
    if (lo > hi) return null;
    int mid = (lo + hi) >>> 1;
    TreeNode node = new TreeNode(a[mid]);
    node.left = build(a, lo, mid - 1);
    node.right = build(a, mid + 1, hi);
    return node;
}

TreeNode* build(vector<int>& a, int lo, int hi) {
    if (lo > hi) return nullptr;
    int mid = (lo + hi) / 2;
    TreeNode* node = new TreeNode(a[mid]);
    node->left = build(a, lo, mid - 1);
    node->right = build(a, mid + 1, hi);
    return node;
}
TreeNode* sortedToBST(vector<int>& nums) {
    return build(nums, 0, (int)nums.size() - 1);
}

Time: O(n) Space: O(log n) recursion