# How to Build an Interval Tree

This article will describe the process of building an interval tree, an ordered tree structure that holds intervals and allows to efficiently find all intervals that overlap with any given interval or point. This article will guide you through designing an object-oriented structure that will represent and support an interval tree. It will also show you how to implement methods to build an interval tree from an array and search for overlaps.

## Steps

- 1
**Create an Interval class.**This class will contain beginning and ending points and any additional information you will need. - 2
**Create a node class.**As interval tree is a tree-based structure (generally, a collection of nodes with some restrictions), you need to design a node class, which will contain:- A center point
- A collection of intervals overlapping the center point sorted by their beginning point
- A collection of intervals overlapping the center point sorted by their ending point
- A reference to a node containing all intervals completely to the left of the center point (left child)
- A reference to a node containing all intervals completely to the right of the center point (right child).

- 3
**Create an interval tree class.**This class will represent the interval tree and will contain:- A root node
- A method that will facilitate building a tree from an array (to be implemented in step 4).
- A search method that will find all overlaps of a given point or interval with the intervals in the tree (to be implemented in step 5).
- A find median method, which will find a center point for a given array of intervals (to be implemented in step 6).

- 4
**Implement the build method.**This method will take an array of intervals and build an interval tree in O(N*logN) time complexity. You need to perform these steps:- Find a median of the whole array of intervals.
- Divide all the intervals into 3 groups:
- Intervals that lie completely to the left from the center point
- Intervals that lie completely to the right from the center point
- Intervals that overlap the center point

- Add the overlapping intervals into the collections of intervals sorted by their beginning and ending points
- Recursively execute this method for the arrays of intervals lying completely to the left/right from the center point, add these nodes as root left/right child.

- 5
**Implement the search method.**This method will take a point, for which all overlapping intervals should be found, and return an array of these intervals in O(logN + X) time complexity, where X is the number of overlapping intervals. You need to perform these steps:- Starting from the root node, check if the given point is to the right/left from the center point
- Depending on the given point (whether it is to the left/right from the center point), go through the arrays of intervals that overlap the center point and add them to the result array while their beginning/ending point is less/more than the given point respectively
- Depending on the given point (whether it is to the left/right from the center point), recursively execute this method for the left/right child.

- 6
**Implement the find median method.**This method will take an array of intervals and return a center point for this array in O(N) time complexity. Note, there are several implementations of this method, but one of the easiest consists of the following steps:- For each interval count its median
- Count the average of all intervals' medians.

## Sources and Citations

- The complete code in Python is available here: https://github.com/LordPatriot/itree

## Article Info

Categories: Mathematics | Programming