Parent nodes correspond to union of subregions in children

Partitioned space containing data points:

Tree that induced above partitioning:

Above has no overlap among subregions; some partitioning schemes permit overlap.

Above uses hyper-rectangles for partitioning; other shapes (e.g. spheres, convex polyhedra) have been used.

Detailed summary/comparison of tree methods can be found in [White & Jain] , [Kurniawati et al.]