Min-Height BST

Tags

Min-Height BST

Category

Binary Search Trees (BST)

Difficulty

Medium

Problem Statement

Given a sorted (ascending) array of distinct integers, construct a Binary Search Tree (BST) with the minimum possible height. The BST must contain all elements from the input array. Return the root of the constructed BST.

Intuition

A BST has minimum height when it is as balanced as possible. To achieve this, we want roughly equal numbers of nodes in the left and right subtrees at every level. Since the array is already sorted, the middle element is the ideal root: all elements to its left are smaller (left subtree) and all elements to its right are larger (right subtree). Applying this logic recursively to each half produces a balanced BST.

This is essentially a divide-and-conquer approach. By always picking the median as the root, we guarantee that the tree height is O(log n).

Approach

  1. If the array (or current subarray) is empty, return null.
  2. Find the middle index of the current subarray.
  3. Create a new BST node with the value at the middle index.
  4. Recursively construct the left subtree from elements to the left of the middle.
  5. Recursively construct the right subtree from elements to the right of the middle.
  6. Return the created node.

Pseudocode

function minHeightBST(array):
    return buildBST(array, 0, length(array) - 1)

function buildBST(array, low, high):
    if low > high:
        return null
    mid = (low + high) / 2  // integer division
    node = new BSTNode(array[mid])
    node.left = buildBST(array, low, mid - 1)
    node.right = buildBST(array, mid + 1, high)
    return node

Time & Space Complexity

  • Time: O(n), where n is the number of elements. Each element is visited exactly once to create its node.
  • Space: O(n) for the BST itself. The recursion call stack uses O(log n) space since the tree is balanced.

Key Insights

  • The sorted array property is critical: it lets us identify the correct root for any subtree in O(1) by picking the middle element.
  • This algorithm produces the same result as inserting elements level by level into a BST.
  • The resulting tree has height floor(log2(n)), which is the theoretical minimum for n nodes.
  • If there is an even number of elements, either of the two middle elements can be chosen as the root; both yield a valid min-height BST.

Edge Cases

  • Empty array: return null.
  • Single element: return a tree with one node (no children).
  • Two elements: the tree will have height 1, with one child on either the left or right depending on which middle index is chosen.
  • Array with negative numbers: works identically since the algorithm depends only on sorted order, not the values themselves.
  • Very large arrays: recursion depth is O(log n), so stack overflow is not a practical concern.

Linked mentions