# Implementing an interval tree using arrays?

Is it possible to create an interval tree using an array instead of the traditional pointer method? I know that for segment trees this is commonly done where the children of any element with index i are stored in 2i and 2i + 1 and the range is halved. For interval trees however, because the ranges added are not guaranteed to be halved each time, it seems like it might not be possible.

Could anyone prove or disprove whether interval trees can be implemented in this manner?

• They probably can, but the interesting question is at what cost. – Raphael Mar 9 '15 at 8:05

Binary trees can be implemented, as you say, storing children of node $i$ at indices $2i$ and $2i+1$. This is sometimes called an implicit representation as no explicit structure is stored. The method is alwaus possible, but only advisable when the tree is perfect (all levels completely filled) or near perfect, like the complete trees used to store a binary heap. Otherwise it is a waste of space. When some node $i$ is missing in the tree then also nodes $2i$ and $2i+1$ are missing, and $4i,\dots, 4i+4$, etc.