☕ DSA Java Articles

Topics › Binary Search Trees › Practice Problems

Construct BST from given keys

Easy TUF ID 2391 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given the keys of a binary search tree as an integer array sorted in strictly increasing order. Build a height-balanced BST containing exactly these keys and return its root. Height-balanced means that, for every node, the heights of its left and right subtrees differ by at most one.

This is the problem the SDE sheet links under this title (LeetCode 108, “Convert Sorted Array to Binary Search Tree”). Several trees can be correct for the same input; the methods here always choose the left-middle key as the root of each range, which is one accepted answer. If your keys arrive unsorted, sort them first and then apply the same construction.

Constraints (LeetCode 108): 1 ≤ n ≤ 10^4, values in [-10^4, 10^4], strictly increasing. The Java file also handles an empty array, extreme int values, and 100000 keys.

Example 1

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

answer:      0
            / \
         -10   5
            \   \
            -3   9

0 is the middle key. The keys smaller than it, [-10, -3], form the left subtree, and [5, 9] the right subtree, each built the same way. [0, -3, 9, -10, null, 5] (right-middle choices) would also be accepted.

Example 2

keys = [1, 3]
answer: 1 with right child 3      // 3 with left child 1 is equally valid

Why not just insert the keys one by one? Standard BST insertion of a sorted sequence puts every new key to the right of all previous ones, producing a chain of height n. It is a valid BST, but searching it costs O(n), which defeats the purpose of a search tree. Balance has to come from choosing the root carefully.

Approach 1: Middle key as root, recursing on copied halves

Intuition. For a tree to be balanced, the root must split the keys into two halves of (almost) equal size, so the root should be the median. Because the array is sorted, the median is simply the middle element, everything before it is smaller (it belongs in the left subtree), and everything after it is larger (the right subtree). Each half is again a sorted array, so the same rule builds each subtree.

Why is the result balanced? The two halves have sizes that differ by at most one. A tree built this way from m keys has height floor(log2 m) + 1, and that number does not decrease as m grows, so two halves whose sizes differ by one have heights that differ by at most one. Applying this at every node gives the height-balance property, and the overall height is the minimum possible for n nodes.

The most literal implementation passes the two halves as new arrays.

Algorithm.

  1. If the array is empty, return null.
  2. Let mid = (length - 1) / 2 (the left-middle index) and make keys[mid] the root.
  3. Build the left child from a copy of keys[0..mid-1] and the right child from a copy of keys[mid+1..].
static TreeNode bruteForce(int[] keys) {
    if (keys.length == 0) return null;
    int mid = (keys.length - 1) / 2;                                  // left-middle for even lengths
    TreeNode root = new TreeNode(keys[mid]);
    root.left = bruteForce(Arrays.copyOfRange(keys, 0, mid));
    root.right = bruteForce(Arrays.copyOfRange(keys, mid + 1, keys.length));
    return root;
}

Complexity. Time O(n log n): on each level of the recursion the copied pieces add up to about n elements, and there are about log2 n levels. Space O(n) extra: the copies alive at one time are the arrays along one root-to-leaf path, of sizes about n/2, n/4, ..., which sum to less than n. The n tree nodes themselves are the output.

Approach 2: Optimal, recurse on index bounds

Intuition. The copies carry no information that two indices cannot carry. Describe each subarray by its bounds lo and hi in the original array and pick the middle index inside them. The tree produced is exactly the same as in Approach 1 (the tests check this), but each call now does constant work.

Algorithm.

  1. build(lo, hi): if lo > hi, return null.
  2. mid = lo + (hi - lo) / 2; create the root from keys[mid].
  3. root.left = build(lo, mid - 1), root.right = build(mid + 1, hi).
  4. Start with build(0, n - 1).
static TreeNode optimal(int[] keys) {
    return build(keys, 0, keys.length - 1);
}

static TreeNode build(int[] keys, int lo, int hi) {
    if (lo > hi) return null;
    int mid = lo + (hi - lo) / 2;                                     // same left-middle choice as above
    TreeNode root = new TreeNode(keys[mid]);
    root.left = build(keys, lo, mid - 1);                            // keys smaller than keys[mid]
    root.right = build(keys, mid + 1, hi);                           // keys larger than keys[mid]
    return root;
}

Dry run on Example 1:

call mid node created children calls
build(0, 4) 2 0 build(0, 1), build(3, 4)
build(0, 1) 0 -10 build(0, -1) = null, build(1, 1)
build(1, 1) 1 -3 both empty
build(3, 4) 3 5 build(3, 2) = null, build(4, 4)
build(4, 4) 4 9 both empty

Complexity. Time O(n): one call per key plus one per empty range, each constant work. Space O(log n) for the recursion, because the tree being built is balanced and the recursion depth equals its height.

Edge cases and pitfalls