Skip to content
Tutorials Center
My learning

Topics

Lesson 202 of 225 ยท Advanced Topics

Interval Trees, k-d Trees and Quadtrees

Learn spatial and interval queries: find overlapping intervals with an interval tree, nearest neighbors with a k-d tree, and range searches with a quadtree, in Python.

Not all data fits on a single number line. A calendar app must find every meeting that overlaps 3:15 PM. A map app must find the cafรฉ closest to you. A game engine must find every enemy inside a rectangle on screen. Scanning all items for each question costs O(n), which is fine for a hundred items and painful for a million.

This lesson introduces three structures that organize intervals and points in space so such queries touch only a small part of the data: the interval tree (1-D intervals), the k-d tree (points in k dimensions, great for nearest neighbor), and the quadtree (2-D space split into four quadrants). All three are cousins of the binary search tree and the segment tree: split the problem in half, and skip whole halves that cannot contain the answer.

Interval trees: which intervals contain this point?

An interval is a pair (lo, hi), like a meeting from 9 to 11. The stabbing query asks: which intervals contain the point x?

A centered interval tree works like this:

  1. Pick a center value (the median of all endpoints).
  2. Intervals entirely to the left of the center go in the left subtree, those entirely to the right go in the right subtree.
  3. Intervals that cross the center stay in this node, stored twice: sorted by start and sorted by end.
flowchart TD
    N["center = 10<br/>crossing: (8,12) (9,10) (5,10) (10,15)"]
    N --> L["left subtree<br/>intervals ending before 10"]
    N --> R["right subtree<br/>intervals starting after 10"]

A node keeps the intervals that cross its center. The rest are sent left or right.

To answer a query for x:

  • If x is left of the center, a crossing interval contains x exactly when its start is <= x. Scan the list sorted by start and stop at the first start above x. Then recurse into the left subtree.
  • If x is right of the center, scan the list sorted by end from the largest down while the end is >= x, then recurse right.
  • If x equals the center, every crossing interval contains it, and you are done.

Only one path from root to leaf is followed, and each scan reports only real answers. The query costs O(log n + k), where k is the number of intervals reported.

Python A centered interval tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Finding intervals that overlap a query interval [a, b] is a small extension: an interval overlaps [a, b] if it contains a, or if it starts inside (a, b]. Many libraries therefore combine an interval tree with a sorted list of starts. A different but popular approach is an augmented balanced BST keyed by interval start, where each node also stores the maximum end in its subtree; that supports insertions and deletions, which this static tree does not (see balanced trees).

k-d trees: nearest neighbor in k dimensions

A k-d tree is a binary search tree for points with k coordinates. Each level splits on one coordinate, cycling through the axes: x at the root, y at the next level, x again, and so on. The splitting value is the median, so the tree stays balanced.

Nearest-neighbor search uses a simple rule: walk down toward where the target would live, remember the best point so far, and on the way back up visit the other side only if the splitting line is closer than the current best distance. That prune throws away large regions.

flowchart TD
    A["split on x at x=50"] --> B["left: x < 50<br/>split on y"]
    A --> C["right: x >= 50<br/>split on y"]
    B --> D["split on x ..."]
    B --> E["split on x ..."]
    C --> F["split on x ..."]
    C --> G["split on x ..."]

Each level splits the remaining points on the next axis.

Python k-d tree nearest neighbor versus a full scan

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In low dimensions (2 to about 10) a k-d tree finds the nearest neighbor in roughly O(log n) on average. In very high dimensions pruning stops working, the so-called curse of dimensionality, and approximate methods take over. Worst-case behavior is O(n), and inserting points one by one unbalances the tree, so build it from the full set when possible.

A range query (all points inside a rectangle) works similarly: descend, but skip a child whenever the splitting line shows the child's region cannot intersect the rectangle.

Quadtrees: recursive squares

A quadtree splits a square region into four equal quadrants (NW, NE, SW, SE) when it holds too many points. Each leaf stores up to a fixed capacity of points; when a leaf overflows, it becomes an internal node with four children and its points are pushed down.

Unlike the k-d tree, the split positions come from the geometry (halving the square), not from the data. That makes quadtrees easy to update and a natural fit for maps, collision detection and image compression. In 3-D the same idea uses eight children and is called an octree.

A rectangle query skips any quadrant whose square does not overlap the rectangle.

Python A point quadtree with rectangle queries

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The MAX_DEPTH guard matters: if many points share the same coordinates, a plain quadtree would split forever.

Which one should you use?

Structure Data Typical query Strength
Interval tree 1-D intervals Which intervals contain or overlap x? O(log n + k)
k-d tree k-D points Nearest neighbor, range search Balanced from median splits
Quadtree / octree 2-D / 3-D points or regions Rectangle search, collisions Easy to update, matches geometry
Segment tree Array positions Range sums, minimums Updates and aggregates

For production work you rarely write these yourself: databases use R-trees and spatial indexes, and libraries such as SciPy offer a cKDTree. Knowing how they work tells you when each is appropriate. Many problems also need the basic distance and area formulas from geometry basics.

Common mistakes

  • Treating a k-d tree as dynamic. Inserting sorted data one by one produces a long chain. Build from all points, or rebuild periodically.
  • Pruning on the wrong value. Compare the squared axis distance with the squared best distance; mixing a plain distance with a squared one prunes incorrectly.
  • Using a k-d tree in hundreds of dimensions. Pruning fails; use approximate nearest neighbor methods.
  • No depth limit in a quadtree. Duplicate points make it split without end.
  • Mixing closed and half-open intervals. Decide whether (9, 11) contains 11 and use the same rule in build and query.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In a centered interval tree, which intervals does a node store itself?

    Intervals entirely left or right are passed to the child subtrees; only the crossing ones stay.
  2. 2. What is the query time to report k intervals containing a point in an interval tree with n intervals?

    One root-to-leaf path is followed and each scan reports only genuine answers.
  3. 3. How does a k-d tree choose the axis to split on?

    Depth modulo k picks the axis, alternating x, y, x, y, ... in two dimensions.
  4. 4. When may nearest-neighbor search skip the far side of a split?

    Every point on the far side is at least as far as the splitting line, so none can beat the best found.
  5. 5. Why does a quadtree implementation need a maximum depth?

    Points with equal coordinates always fall in the same quadrant, so splitting never separates them.

Summary

  • An interval tree stores crossing intervals at each node, sorted two ways, and answers stabbing queries in O(log n + k).
  • A k-d tree splits points by the median on alternating axes; nearest-neighbor search prunes sides that cannot beat the best distance.
  • A quadtree (octree in 3-D) splits space into equal quadrants and skips quadrants that miss the query rectangle.
  • k-d and interval trees here are built once; quadtrees take insertions easily.
  • Pruning is the common idea: use geometry to ignore big chunks of the data.

Next: Project: Autocomplete Engine