Convert a Sorted Array to a Balanced BST

Given an array sorted in ascending order, build a height-balanced binary search tree from it: for every node, the heights of its two subtrees differ by at most one.

LeetCode: 108. Convert Sorted Array to Binary Search Tree

Example

Text

Input:  [-10, -3, 0, 5, 9]

Output (one valid answer):
        0
       / \
     -3   9
     /   /
   -10  5

Brute force: insert the values in order

Inserting each value with the usual BST insert produces a valid BST, but not a balanced one. With sorted input, every new value is larger than everything so far and goes to the far right, so the tree becomes a chain.

A tree node here is an object with left and right references. An empty subtree is null, so no wrapper type is needed.

Java

public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    static TreeNode insert(TreeNode root, int val) {
        TreeNode node = new TreeNode(val);
        if (root == null) return node;
        TreeNode cur = root;
        while (true) {
            if (val < cur.val) {
                if (cur.left == null) { cur.left = node; break; }
                cur = cur.left;
            } else {
                if (cur.right == null) { cur.right = node; break; }
                cur = cur.right;
            }
        }
        return root;
    }

    static int height(TreeNode root) {
        if (root == null) return -1;
        return 1 + Math.max(height(root.left), height(root.right));
    }

    public static void main(String[] args) {
        TreeNode root = null;
        for (int v : new int[] {-10, -3, 0, 5, 9}) {
            root = insert(root, v);
        }
        System.out.println("height " + height(root));
    }
}

Output

height 4

Time: O(n²), because each insert walks the whole chain. Height: n - 1, so later searches cost O(n) too. A self-balancing tree (such as java.util.TreeMap, which is a red-black tree) avoids this, but the problem asks for a plain BST.

Optimal: the middle element as the root

The middle element of the array has half the values on each side, so it's the right root. The left half becomes the left subtree and the right half the right subtree, built the same way recursively. Both halves differ in size by at most one, which keeps every node balanced.

Java

public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    // Builds from nums[lo..hi), the half-open range lo <= i < hi.
    static TreeNode build(int[] nums, int lo, int hi) {
        if (lo >= hi) return null;
        int mid = lo + (hi - lo) / 2;
        return new TreeNode(nums[mid], build(nums, lo, mid), build(nums, mid + 1, hi));
    }

    static TreeNode sortedArrayToBst(int[] nums) {
        return build(nums, 0, nums.length);
    }

    static int height(TreeNode root) {
        if (root == null) return -1;
        return 1 + Math.max(height(root.left), height(root.right));
    }

    static String show(TreeNode t) {
        if (t == null) return "_";
        if (t.left == null && t.right == null) return String.valueOf(t.val);
        return t.val + "(" + show(t.left) + ", " + show(t.right) + ")";
    }

    public static void main(String[] args) {
        TreeNode root = sortedArrayToBst(new int[] {-10, -3, 0, 5, 9});
        System.out.println(show(root) + " height " + height(root));
        int[] big = new int[1_000_000];
        for (int i = 0; i < big.length; i++) big[i] = i;
        System.out.println("height " + height(sortedArrayToBst(big)));
    }
}

Output

0(-3(-10, _), 9(5, _)) height 2
height 19

Time: O(n): each element becomes one node. Space: O(log n) for the recursion, plus the tree itself.

The recursion passes index bounds lo and hi instead of copying subarrays, so nothing is copied. (Arrays.copyOfRange would copy each half and make the build O(n log n).) lo + (hi - lo) / 2 is the middle index and cannot overflow. A million values give a height of 19, the minimum possible (⌊log₂ 1,000,000⌋). The recursion depth stays near 20, so the thread stack is not a concern.

Edge cases

Empty array: null.
Even length: either middle element works. lo + (hi - lo) / 2 picks the upper one; lo + (hi - lo - 1) / 2 picks the lower one, and both give valid answers.