Convert Sorted Array to Binary Search Tree

easy tree bst divide and conquer

Problem

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.

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_array_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 sortedArrayToBST(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 sortedArrayToBST(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* sortedArrayToBST(vector<int>& nums) {
    return build(nums, 0, (int)nums.size() - 1);
}

Explanation

We want a height-balanced BST from a sorted array. The trick is to always pick the middle element as the root: with roughly half the values on each side, the left and right subtrees end up the same height.

The helper build(lo, hi) works on the slice nums[lo..hi]. If lo > hi the slice is empty and we return null. Otherwise we take mid = (lo + hi) / 2 as this subtree's root.

Then we recurse: the left half [lo, mid - 1] builds the left child and the right half [mid + 1, hi] builds the right child. Because the array is sorted, everything left of mid is smaller and everything right is larger, so the BST ordering is automatic.

Example: nums = [-10, -3, 0, 5, 9]. Middle index 2 gives root 0. The left half [-10, -3] picks -3 as root with -10 as its left child; the right half [5, 9] picks 9 with 5 as its left child.

Splitting at the middle every time keeps the tree balanced and visits each element once, so it runs in linear time.

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