Building the Tree

To build an interval tree:

function buildIntervalTree(intervals)
    if intervals is empty then
        return null

    // Find midpoint of all endpoints
    allPoints := collect all low and high values
    mid := median of allPoints

    // Partition intervals
    center := intervals containing mid
    left := intervals entirely < mid
    right := intervals entirely > mid

    node := new IntervalTreeNode()
    node.mid := mid
    node.center := center (sorted by low and by high)
    node.left := buildIntervalTree(left)
    node.right := buildIntervalTree(right)
    return node

Using the median ensures balanced trees. Time: $O(n \log n)$. Space: $O(n)$.