Introduction

A sorted array already gives us the order. Choosing its middle value first gives the tree two smaller, more evenly sized problems. Repeating this process usually gives the initial tree a smaller height, so searching it does not have to follow a long one-sided chain.

Why the middle matters

A sorted array already tells us the relative order of every value. If the middle value becomes the root, values before it form the left part of the tree and values after it form the right part. Repeating that decision gives the two sides similar numbers of values and therefore a shallow initial tree.

For example, in [1, 3, 5, 7, 9, 11, 13], the middle value is 7. Values smaller than 7 belong on the left, and values larger than 7 belong on the right. The middle values of those two sections then become 3 and 11.

The Binary-Search-Tree repository follows this approach in buildTree(array). It first removes duplicates with Set, sorts numerically, and then recursively builds nodes from index ranges. The constructor uses that method for its initial root.

Sorted array ranges mapped to midpoint roots and left/right subtrees

The recursive mental model

For a sorted range from start to end, where the numbers represent array positions:

  1. If start is greater than end, there is no value, so return null.
  2. Compute the middle index of that range.
  3. Create a node from that middle value.
  4. Build its left child from start through mid - 1.
  5. Build its right child from mid + 1 through end.
  6. Return the new node as this range’s subtree root.

The base case is what stops the recursion after every value has become a node or an empty child. Returning subtree roots lets the parent attach each result to left or right. This is the same recursive idea used in the deletion article: a function processes one subtree and returns the node that should represent it.

One small walk-through

Take the sorted unique values [1, 3, 5, 7, 9, 11, 13]. The midpoint is 7, so it becomes the root. The left range produces 3, with 1 and 5 below it. The right range produces 11, with 9 and 13 below it.

The important part is not memorising the final shape. It is seeing that every recursive call receives a smaller range of array positions and that no range includes the value already selected as its parent.

Why sorted input is essential

The midpoint only divides the values meaningfully when the array is sorted according to the same comparison policy used by the tree. The repository sorts numeric values with (a, b) => a - b and removes duplicates before selecting midpoints. Passing unsorted values directly to the range builder would not establish the BST invariant.

The repository also contains buildTreeLoop(array), a breadth-first construction that stores nodes and their ranges in a queue. It applies the same sorted-unique input and midpoint idea; the recursive buildTree is the method used by the constructor.

Ranges versus slicing

An implementation can recurse with index pairs, as this repository does, or create new arrays by slicing the left and right pieces at every step. Index ranges avoid copying the values for each subproblem. The recursion still uses stack space proportional to tree height, while the node objects and the sorted unique array occupy the data storage.

Repeated slicing can make the code look direct, but it allocates and copies additional arrays. That changes the auxiliary-space and practical-cost discussion even though the resulting tree shape is the same.

Rebuilding an existing tree

The repository’s rebalance() method collects values through inorder traversal, then calls the midpoint builder on that sorted sequence. The workflow is therefore:

  1. traverse the existing BST inorder;
  2. use the resulting sorted values as input; and
  3. replace the root with a newly built midpoint tree.

This is a rebuild operation. It does not turn the tree into an AVL or red-black tree that automatically rotates after every insertion. Later inserts can make the rebuilt tree uneven again.

Complexity

For n input values, duplicate removal and numeric sorting cost O(n log n) in the usual comparison-sort model. The recursive construction then creates each unique node once, O(n) time, with O(h) call-stack space where h is the resulting height. The repository retains the sorted unique array while constructing, so total auxiliary memory also includes that array.

The midpoint strategy aims for a small, approximately logarithmic height when the values are distributed across the ranges. However, “balanced” here means that the construction starts with similar-sized subproblems. It is not a guarantee about all future insertions or deletions.

A note about height conventions

The repository’s public height() method returns -1 for an empty subtree, making a leaf height 0. Its separate balance helper uses 0 as the height of an empty subtree. Those are local conventions in two different calculations; an explanation or test should not silently substitute one for the other.

Reflection

The midpoint rule made tree construction feel less like pointer manipulation and more like preserving a set of shrinking intervals. Once the range and base case are clear, each node has a simple responsibility: choose its value, delegate the two smaller ranges, and connect the returned subtrees.

Key takeaways

  • Sorting and duplicate removal happen before the repository chooses midpoint roots.
  • The base case is an empty index range, which returns null.
  • Index ranges avoid the repeated copying caused by array slicing.
  • rebalance() obtains sorted values with inorder traversal, then rebuilds from midpoints.
  • The result is a balanced initial/rebuilt BST, not a self-balancing AVL or red-black tree.

Sources