Interval, Range & Spatial Search Trees

                Mastery target: Level A recognition, progressing toward Level B implementation. You should be able to pick the right structure for "does anything overlap this interval?", "what's the nearest point?", and "what's inside this rectangle?" — and justify the choice from each structure's query cost.
            

1. Introduction & Motivation

Every structure covered earlier in this series answers a question about a single key: is this value present, what is the predecessor of this key, is this key smaller than that one. Many real problems ask a different kind of question entirely: how do you index data so you can efficiently query a range or region, not just a single point?

That single framing question splits into three related but distinct problems, each of which needs its own structure:

1D ranges of intervals: "does any stored interval overlap $[lo, hi]$?" — two meetings that share time, two genomic segments that overlap. This is the Interval Tree.
1D ranges of points: "which stored points fall between $lo$ and $hi$?" — a sorted set of single numbers, queried repeatedly for sub-ranges. This is the Range Tree.
Multi-dimensional regions: "which points or objects lie in this 2D (or 3D) box, or which one is closest to here?" — this is the domain of the k-d Tree, Quadtree/Octree, and R-Tree.

These structures share a family resemblance: nearly all of them are trees that store extra summary information at each node (an augmented BST, or a spatial subdivision) so that an entire subtree can be included or excluded from the answer without visiting every element inside it. That pruning step is the idea to watch for in every section below.

2. Prerequisites

This lesson assumes comfort with basic binary search trees: node structure, recursive insert, and the BST ordering property. If augmented BSTs — trees where each node stores extra derived information alongside its key — are unfamiliar, review the node structure and insertion walkthrough in Part 10: BST & Balanced Trees before continuing; the Interval Tree and Range Tree below are both augmented BSTs built directly on that foundation.

One distinction is worth making explicit up front: the Fenwick Tree and Segment Tree also answer "range" queries, but over a single sorted array index — range-sum, range-min, range-max on positions $0 \ldots n-1$. The structures in this lesson instead answer overlap queries between intervals, and range/region queries over point coordinates that don't already live at fixed array positions — a different problem shape, even though the word "range" shows up in both.

3. Interval Tree

                Core insight: An Interval Tree is an augmented BST keyed on each interval's start (low endpoint). Every node additionally stores max_end: the largest high endpoint anywhere in its subtree. During an overlap query, if a subtree's max_end is smaller than the query's low endpoint, nothing in that entire subtree can possibly overlap — so it is pruned without being visited.
            

Two intervals $[a, b]$ and $[c, d]$ overlap exactly when $a \le d$ and $c \le b$. The search walks down from the root: at each node, it checks whether the node's own interval overlaps the query; if not, it uses max_end to decide whether the left subtree could possibly contain an overlap, and only descends into the right subtree otherwise.

Worked Example

Hand-trace an overlap query

Insert, in order, the intervals (15,20), (10,30), (17,19), (5,8), (12,15), (30,40) keyed by low endpoint. The resulting tree (with each node's max_end):

Node	Interval	Parent	max_end
root	(15,20)	—	40
left of root	(10,30)	(15,20)	30
left of (10,30)	(5,8)	(10,30)	8
right of (10,30)	(12,15)	(10,30)	15
right of root	(17,19)	(15,20)	40
right of (17,19)	(30,40)	(17,19)	40

Query overlap of [22, 25]: at root (15,20), $15 \le 25$ but $22 \le 20$ is false, so no overlap here. Left child's max_end is 30, and $30 \ge 22$, so descend left to (10,30). There, $10 \le 25$ and $22 \le 30$ — overlap found. The query never visits (5,8), (12,15), (17,19), or (30,40): four of six nodes were pruned by a single max_end comparison.

class IntervalNode:
    def __init__(self, low, high):
        self.low = low
        self.high = high
        self.max_end = high
        self.left = None
        self.right = None


class IntervalTree:
    def __init__(self):
        self.root = None

    def insert(self, low, high):
        self.root = self._insert(self.root, low, high)

    def _insert(self, node, low, high):
        if node is None:
            return IntervalNode(low, high)
        if low < node.low:
            node.left = self._insert(node.left, low, high)
        else:
            node.right = self._insert(node.right, low, high)
        node.max_end = max(node.max_end, high)
        return node

    def search_overlap(self, low, high):
        """Return one interval overlapping [low, high], or None."""
        return self._search(self.root, low, high)

    def _search(self, node, low, high):
        if node is None:
            return None
        if node.low <= high and low <= node.high:
            return (node.low, node.high)
        if node.left is not None and node.left.max_end >= low:
            return self._search(node.left, low, high)
        return self._search(node.right, low, high)


tree = IntervalTree()
for interval in [(15, 20), (10, 30), (17, 19), (5, 8), (12, 15), (30, 40)]:
    tree.insert(*interval)

print(tree.search_overlap(22, 25))  # (10, 30) -- overlaps [22, 25]
print(tree.search_overlap(41, 45))  # None -- nothing overlaps [41, 45]

#include <iostream>
#include <memory>
#include <vector>
#include <utility>
#include <algorithm>

struct IntervalNode {
    int low, high, max_end;
    std::unique_ptr<IntervalNode> left, right;
    IntervalNode(int lo, int hi) : low(lo), high(hi), max_end(hi) {}
};

class IntervalTree {
public:
    void insert(int low, int high) {
        root = insertNode(std::move(root), low, high);
    }

    // Returns true and fills (outLow, outHigh) with one overlapping interval.
    bool searchOverlap(int low, int high, int& outLow, int& outHigh) const {
        return search(root.get(), low, high, outLow, outHigh);
    }

private:
    std::unique_ptr<IntervalNode> root;

    std::unique_ptr<IntervalNode> insertNode(std::unique_ptr<IntervalNode> node, int low, int high) {
        if (!node) {
            return std::make_unique<IntervalNode>(low, high);
        }
        if (low < node->low) {
            node->left = insertNode(std::move(node->left), low, high);
        } else {
            node->right = insertNode(std::move(node->right), low, high);
        }
        node->max_end = std::max(node->max_end, high);
        return node;
    }

    bool search(const IntervalNode* node, int low, int high, int& outLow, int& outHigh) const {
        if (!node) {
            return false;
        }
        if (node->low <= high && low <= node->high) {
            outLow = node->low;
            outHigh = node->high;
            return true;
        }
        if (node->left && node->left->max_end >= low) {
            return search(node->left.get(), low, high, outLow, outHigh);
        }
        return search(node->right.get(), low, high, outLow, outHigh);
    }
};

int main() {
    IntervalTree tree;
    std::vector<std::pair<int, int>> intervals = {{15,20},{10,30},{17,19},{5,8},{12,15},{30,40}};
    for (auto& iv : intervals) {
        tree.insert(iv.first, iv.second);
    }

    int lo, hi;
    if (tree.searchOverlap(22, 25, lo, hi)) {
        std::cout << "Overlaps with [" << lo << ", " << hi << "]\n"; // [10, 30]
    }
    if (!tree.searchOverlap(41, 45, lo, hi)) {
        std::cout << "No overlap with [41, 45]\n";
    }
}

import java.util.Arrays;

public class IntervalTree {
    static class Node {
        int low, high, maxEnd;
        Node left, right;
        Node(int low, int high) {
            this.low = low;
            this.high = high;
            this.maxEnd = high;
        }
    }

    private Node root;

    public void insert(int low, int high) {
        root = insert(root, low, high);
    }

    private Node insert(Node node, int low, int high) {
        if (node == null) {
            return new Node(low, high);
        }
        if (low < node.low) {
            node.left = insert(node.left, low, high);
        } else {
            node.right = insert(node.right, low, high);
        }
        node.maxEnd = Math.max(node.maxEnd, high);
        return node;
    }

    /** Returns one interval overlapping [low, high], or null. */
    public int[] searchOverlap(int low, int high) {
        return search(root, low, high);
    }

    private int[] search(Node node, int low, int high) {
        if (node == null) {
            return null;
        }
        if (node.low <= high && low <= node.high) {
            return new int[] { node.low, node.high };
        }
        if (node.left != null && node.left.maxEnd >= low) {
            return search(node.left, low, high);
        }
        return search(node.right, low, high);
    }

    public static void main(String[] args) {
        IntervalTree tree = new IntervalTree();
        int[][] intervals = { {15, 20}, {10, 30}, {17, 19}, {5, 8}, {12, 15}, {30, 40} };
        for (int[] iv : intervals) {
            tree.insert(iv[0], iv[1]);
        }

        System.out.println(Arrays.toString(tree.searchOverlap(22, 25))); // [10, 30]
        System.out.println(tree.searchOverlap(41, 45)); // null
    }
}

4. Range Tree (1D)

A balanced BST over sorted points

A 1D Range Tree is a perfectly balanced BST built from a sorted set of points, where the median point becomes the root and the two halves recurse into the left and right subtrees. A range query $[lo, hi]$ first walks down from the root to find the split node — the last node where the search paths toward $lo$ and toward $hi$ still agree. Below the split node, the path toward $lo$ peels left and the path toward $hi$ peels right; every subtree hanging off the "inside" of each path is a canonical subtree that is entirely inside $[lo, hi]$, so it can be reported wholesale without checking each of its points individually. This gives a query time of $O(\log n + k)$, where $n$ is the number of stored points and $k$ is the number of points actually returned.

A 2D Range Tree extends this idea by attaching, to every node of the primary tree (built on the x-coordinate), a secondary Range Tree over the y-coordinates of that node's subtree — so an x-range query first finds $O(\log n)$ canonical subtrees, and then a y-range query runs against each of their secondary trees. That layered construction is only sketched here conceptually and is not implemented below; for this lesson's purposes, the k-d Tree in the next section solves the 2D range problem more directly and with a single, more intuitive tree.

class RangeTreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


def build_range_tree(sorted_points):
    if not sorted_points:
        return None
    mid = len(sorted_points) // 2
    node = RangeTreeNode(sorted_points[mid])
    node.left = build_range_tree(sorted_points[:mid])
    node.right = build_range_tree(sorted_points[mid + 1:])
    return node


def _report_subtree(node, result):
    if node is None:
        return
    _report_subtree(node.left, result)
    result.append(node.value)
    _report_subtree(node.right, result)


def _find_split_node(root, low, high):
    node = root
    while node is not None and (node.value < low or node.value > high):
        node = node.right if node.value < low else node.left
    return node


def range_query(root, low, high):
    """Return every stored value in [low, high] in O(log n + k) time."""
    result = []
    split = _find_split_node(root, low, high)
    if split is None:
        return result
    if low <= split.value <= high:
        result.append(split.value)

    node = split.left
    while node is not None:
        if node.value >= low:
            _report_subtree(node.right, result)
            result.append(node.value)
            node = node.left
        else:
            node = node.right

    node = split.right
    while node is not None:
        if node.value <= high:
            _report_subtree(node.left, result)
            result.append(node.value)
            node = node.right
        else:
            node = node.left

    return result


points = sorted([1, 3, 5, 7, 9, 11, 13, 15])
tree = build_range_tree(points)
print(sorted(range_query(tree, 4, 12)))  # [5, 7, 9, 11]

#include <iostream>
#include <vector>
#include <memory>
#include <algorithm>

struct RangeNode {
    int value;
    std::unique_ptr<RangeNode> left, right;
    explicit RangeNode(int v) : value(v) {}
};

std::unique_ptr<RangeNode> buildRangeTree(const std::vector<int>& points, int start, int end) {
    if (start >= end) {
        return nullptr;
    }
    int mid = start + (end - start) / 2;
    auto node = std::make_unique<RangeNode>(points[mid]);
    node->left = buildRangeTree(points, start, mid);
    node->right = buildRangeTree(points, mid + 1, end);
    return node;
}

void reportSubtree(const RangeNode* node, std::vector<int>& result) {
    if (!node) return;
    reportSubtree(node->left.get(), result);
    result.push_back(node->value);
    reportSubtree(node->right.get(), result);
}

const RangeNode* findSplitNode(const RangeNode* root, int low, int high) {
    const RangeNode* node = root;
    while (node && (node->value < low || node->value > high)) {
        node = (node->value < low) ? node->right.get() : node->left.get();
    }
    return node;
}

std::vector<int> rangeQuery(const RangeNode* root, int low, int high) {
    std::vector<int> result;
    const RangeNode* split = findSplitNode(root, low, high);
    if (!split) return result;
    if (low <= split->value && split->value <= high) {
        result.push_back(split->value);
    }

    const RangeNode* node = split->left.get();
    while (node) {
        if (node->value >= low) {
            reportSubtree(node->right.get(), result);
            result.push_back(node->value);
            node = node->left.get();
        } else {
            node = node->right.get();
        }
    }

    node = split->right.get();
    while (node) {
        if (node->value <= high) {
            reportSubtree(node->left.get(), result);
            result.push_back(node->value);
            node = node->right.get();
        } else {
            node = node->left.get();
        }
    }
    return result;
}

int main() {
    std::vector<int> points{1, 3, 5, 7, 9, 11, 13, 15};
    auto root = buildRangeTree(points, 0, static_cast<int>(points.size()));

    auto result = rangeQuery(root.get(), 4, 12);
    std::sort(result.begin(), result.end());
    for (int v : result) {
        std::cout << v << ' '; // 5 7 9 11
    }
    std::cout << '\n';
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class RangeTree {
    static class Node {
        int value;
        Node left, right;
        Node(int value) { this.value = value; }
    }

    static Node build(int[] points, int start, int end) {
        if (start >= end) return null;
        int mid = start + (end - start) / 2;
        Node node = new Node(points[mid]);
        node.left = build(points, start, mid);
        node.right = build(points, mid + 1, end);
        return node;
    }

    static void reportSubtree(Node node, List<Integer> result) {
        if (node == null) return;
        reportSubtree(node.left, result);
        result.add(node.value);
        reportSubtree(node.right, result);
    }

    static Node findSplitNode(Node root, int low, int high) {
        Node node = root;
        while (node != null && (node.value < low || node.value > high)) {
            node = (node.value < low) ? node.right : node.left;
        }
        return node;
    }

    static List<Integer> rangeQuery(Node root, int low, int high) {
        List<Integer> result = new ArrayList<>();
        Node split = findSplitNode(root, low, high);
        if (split == null) return result;
        if (low <= split.value && split.value <= high) {
            result.add(split.value);
        }

        Node node = split.left;
        while (node != null) {
            if (node.value >= low) {
                reportSubtree(node.right, result);
                result.add(node.value);
                node = node.left;
            } else {
                node = node.right;
            }
        }

        node = split.right;
        while (node != null) {
            if (node.value <= high) {
                reportSubtree(node.left, result);
                result.add(node.value);
                node = node.right;
            } else {
                node = node.left;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] points = {1, 3, 5, 7, 9, 11, 13, 15};
        Node root = build(points, 0, points.length);

        List<Integer> result = rangeQuery(root, 4, 12);
        Collections.sort(result);
        System.out.println(result); // [5, 7, 9, 11]
    }
}

5. k-d Tree

                Core insight: A k-d Tree is a BST over multi-dimensional points that alternates which coordinate it splits on at each depth: the root splits on x, its children split on y, their children split on x again, and so on (for k dimensions, cycle through all k axes). Each split partitions space with a hyperplane perpendicular to that axis, recursively carving 2D (or k-D) space into regions.
            

Worked Example

Hand-trace building a k-d tree

Build from the points (3,6), (17,15), (13,15), (6,12), (9,1), (2,7), (10,19), choosing the median of the current axis at each level so the tree stays balanced:

Depth	Axis	Points considered (sorted)	Median chosen
0	x	(2,7),(3,6),(6,12),(9,1),(10,19),(13,15),(17,15)	(9,1) — root
1	y	left half by y: (3,6),(2,7),(6,12)	(2,7) — root's left child
1	y	right half by y: (13,15),(17,15),(10,19)	(17,15) — root's right child
2	x	single points remain	(3,6) and (6,12) as leaves under (2,7)
2	y	single points remain	(13,15) and (10,19) as leaves under (17,15)

The finished tree splits on x at the root, y one level down, x again (not used further here since each subtree bottoms out at depth 2). Notice the axis alternates strictly by depth, never by which coordinate happens to vary more — that's what distinguishes it from a Quadtree, which always splits both axes together at a fixed spatial midpoint.

Nearest-neighbor search descends toward the query point like a normal BST search, recording the closest point seen so far. On the way back up, it only checks the other child's subtree if the distance from the query point to the splitting plane is smaller than the best distance found so far — if the plane itself is farther away than the current best, nothing on the far side of it can possibly be closer, so that whole subtree is pruned.

class KDNode:
    def __init__(self, point, left=None, right=None):
        self.point = point
        self.left = left
        self.right = right


def build_kdtree(points, depth=0):
    if not points:
        return None
    axis = depth % 2
    points = sorted(points, key=lambda p: p[axis])
    mid = len(points) // 2
    node = KDNode(points[mid])
    node.left = build_kdtree(points[:mid], depth + 1)
    node.right = build_kdtree(points[mid + 1:], depth + 1)
    return node


def squared_distance(a, b):
    return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2


def nearest_neighbor(root, target):
    best = [None, float("inf")]  # [point, squared distance]

    def search(node, depth):
        if node is None:
            return
        d = squared_distance(node.point, target)
        if d < best[1]:
            best[0], best[1] = node.point, d

        axis = depth % 2
        diff = target[axis] - node.point[axis]
        near_side, far_side = (node.left, node.right) if diff < 0 else (node.right, node.left)

        search(near_side, depth + 1)
        # Only cross into the far side if the splitting plane could still
        # hide a closer point than the best one found so far.
        if diff * diff < best[1]:
            search(far_side, depth + 1)

    search(root, 0)
    return best[0]


def range_search(node, depth, lo, hi):
    """Return every point with lo[i] <= point[i] <= hi[i] for both axes."""
    if node is None:
        return []
    result = []
    x, y = node.point
    if lo[0] <= x <= hi[0] and lo[1] <= y <= hi[1]:
        result.append(node.point)

    axis = depth % 2
    if node.point[axis] >= lo[axis]:
        result.extend(range_search(node.left, depth + 1, lo, hi))
    if node.point[axis] <= hi[axis]:
        result.extend(range_search(node.right, depth + 1, lo, hi))
    return result


points = [(3, 6), (17, 15), (13, 15), (6, 12), (9, 1), (2, 7), (10, 19)]
tree = build_kdtree(points)

print(nearest_neighbor(tree, (9, 2)))          # (9, 1)
print(sorted(range_search(tree, 0, (0, 0), (10, 15))))  # [(2,7),(3,6),(6,12),(9,1)]

#include <iostream>
#include <vector>
#include <memory>
#include <algorithm>
#include <limits>

struct Point { double x, y; };

struct KDNode {
    Point point;
    std::unique_ptr<KDNode> left, right;
    explicit KDNode(Point p) : point(p) {}
};

std::unique_ptr<KDNode> buildKDTree(std::vector<Point> points, int depth = 0) {
    if (points.empty()) return nullptr;
    int axis = depth % 2;
    std::sort(points.begin(), points.end(), [axis](const Point& a, const Point& b) {
        return axis == 0 ? a.x < b.x : a.y < b.y;
    });
    size_t mid = points.size() / 2;
    auto node = std::make_unique<KDNode>(points[mid]);
    std::vector<Point> left(points.begin(), points.begin() + mid);
    std::vector<Point> right(points.begin() + mid + 1, points.end());
    node->left = buildKDTree(std::move(left), depth + 1);
    node->right = buildKDTree(std::move(right), depth + 1);
    return node;
}

double squaredDistance(const Point& a, const Point& b) {
    double dx = a.x - b.x, dy = a.y - b.y;
    return dx * dx + dy * dy;
}

void nearestNeighbor(const KDNode* node, const Point& target, int depth,
                      Point& best, double& bestDist) {
    if (!node) return;
    double d = squaredDistance(node->point, target);
    if (d < bestDist) {
        bestDist = d;
        best = node->point;
    }

    int axis = depth % 2;
    double diff = (axis == 0) ? (target.x - node->point.x) : (target.y - node->point.y);
    const KDNode* nearSide = diff < 0 ? node->left.get() : node->right.get();
    const KDNode* farSide  = diff < 0 ? node->right.get() : node->left.get();

    nearestNeighbor(nearSide, target, depth + 1, best, bestDist);
    if (diff * diff < bestDist) {
        nearestNeighbor(farSide, target, depth + 1, best, bestDist);
    }
}

void rangeSearch(const KDNode* node, int depth, const Point& lo, const Point& hi,
                  std::vector<Point>& result) {
    if (!node) return;
    if (node->point.x >= lo.x && node->point.x <= hi.x &&
        node->point.y >= lo.y && node->point.y <= hi.y) {
        result.push_back(node->point);
    }
    int axis = depth % 2;
    double value   = (axis == 0) ? node->point.x : node->point.y;
    double loBound = (axis == 0) ? lo.x : lo.y;
    double hiBound = (axis == 0) ? hi.x : hi.y;

    if (value >= loBound) rangeSearch(node->left.get(), depth + 1, lo, hi, result);
    if (value <= hiBound) rangeSearch(node->right.get(), depth + 1, lo, hi, result);
}

int main() {
    std::vector<Point> points{{3,6},{17,15},{13,15},{6,12},{9,1},{2,7},{10,19}};
    auto root = buildKDTree(points);

    Point target{9, 2};
    Point best{};
    double bestDist = std::numeric_limits<double>::infinity();
    nearestNeighbor(root.get(), target, 0, best, bestDist);
    std::cout << "Nearest to (9, 2): (" << best.x << ", " << best.y << ")\n"; // (9, 1)

    std::vector<Point> found;
    rangeSearch(root.get(), 0, Point{0, 0}, Point{10, 15}, found);
    std::cout << "Points in [0,10] x [0,15]: ";
    for (auto& p : found) std::cout << "(" << p.x << "," << p.y << ") ";
    std::cout << '\n';
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class KDTree {
    static class Point {
        double x, y;
        Point(double x, double y) { this.x = x; this.y = y; }
        public String toString() { return "(" + x + ", " + y + ")"; }
    }

    static class Node {
        Point point;
        Node left, right;
        Node(Point p) { point = p; }
    }

    static Node build(List<Point> points, int depth) {
        if (points.isEmpty()) return null;
        int axis = depth % 2;
        points.sort((a, b) -> Double.compare(axis == 0 ? a.x : a.y, axis == 0 ? b.x : b.y));
        int mid = points.size() / 2;
        Node node = new Node(points.get(mid));
        node.left = build(new ArrayList<>(points.subList(0, mid)), depth + 1);
        node.right = build(new ArrayList<>(points.subList(mid + 1, points.size())), depth + 1);
        return node;
    }

    static double squaredDistance(Point a, Point b) {
        double dx = a.x - b.x, dy = a.y - b.y;
        return dx * dx + dy * dy;
    }

    static Point best;
    static double bestDist;

    static void nearestNeighbor(Node node, Point target, int depth) {
        if (node == null) return;
        double d = squaredDistance(node.point, target);
        if (d < bestDist) {
            bestDist = d;
            best = node.point;
        }
        int axis = depth % 2;
        double diff = (axis == 0) ? (target.x - node.point.x) : (target.y - node.point.y);
        Node nearSide = diff < 0 ? node.left : node.right;
        Node farSide = diff < 0 ? node.right : node.left;

        nearestNeighbor(nearSide, target, depth + 1);
        if (diff * diff < bestDist) {
            nearestNeighbor(farSide, target, depth + 1);
        }
    }

    static void rangeSearch(Node node, int depth, Point lo, Point hi, List<Point> result) {
        if (node == null) return;
        if (node.point.x >= lo.x && node.point.x <= hi.x &&
            node.point.y >= lo.y && node.point.y <= hi.y) {
            result.add(node.point);
        }
        int axis = depth % 2;
        double value   = (axis == 0) ? node.point.x : node.point.y;
        double loBound = (axis == 0) ? lo.x : lo.y;
        double hiBound = (axis == 0) ? hi.x : hi.y;

        if (value >= loBound) rangeSearch(node.left, depth + 1, lo, hi, result);
        if (value <= hiBound) rangeSearch(node.right, depth + 1, lo, hi, result);
    }

    public static void main(String[] args) {
        List<Point> points = new ArrayList<>(Arrays.asList(
            new Point(3, 6), new Point(17, 15), new Point(13, 15),
            new Point(6, 12), new Point(9, 1), new Point(2, 7), new Point(10, 19)
        ));
        Node root = build(points, 0);

        Point target = new Point(9, 2);
        best = null;
        bestDist = Double.POSITIVE_INFINITY;
        nearestNeighbor(root, target, 0);
        System.out.println("Nearest to (9, 2): " + best); // (9.0, 1.0)

        List<Point> found = new ArrayList<>();
        rangeSearch(root, 0, new Point(0, 0), new Point(10, 15), found);
        System.out.println("Points in range: " + found);
    }
}

6. Quadtree (and Octree)

                Core insight: A Quadtree recursively splits 2D space into four equal quadrants — not by the position of any particular point, like a k-d Tree does, but by a fixed spatial midpoint of the current region. Each quadrant keeps subdividing into its own four quadrants until it holds few enough points (a capacity threshold), at which point it stops.
            

Because the split point is a fixed geometric midpoint rather than a data-dependent median, a Quadtree's shape depends only on the boundary and the capacity, not on insertion order — but it can become unbalanced if points cluster tightly in one quadrant, since that quadrant keeps subdividing while the empty ones do not.

class Rectangle:
    """Axis-aligned box defined by its center (x, y) and half-width/half-height."""
    def __init__(self, x, y, half_w, half_h):
        self.x, self.y, self.half_w, self.half_h = x, y, half_w, half_h

    def contains(self, point):
        px, py = point
        return (self.x - self.half_w <= px <= self.x + self.half_w and
                self.y - self.half_h <= py <= self.y + self.half_h)

    def intersects(self, other):
        return not (other.x - other.half_w > self.x + self.half_w or
                    other.x + other.half_w < self.x - self.half_w or
                    other.y - other.half_h > self.y + self.half_h or
                    other.y + other.half_h < self.y - self.half_h)


class Quadtree:
    def __init__(self, boundary, capacity=4):
        self.boundary = boundary
        self.capacity = capacity
        self.points = []
        self.divided = False

    def subdivide(self):
        x, y = self.boundary.x, self.boundary.y
        w, h = self.boundary.half_w / 2, self.boundary.half_h / 2
        self.northeast = Quadtree(Rectangle(x + w, y - h, w, h), self.capacity)
        self.northwest = Quadtree(Rectangle(x - w, y - h, w, h), self.capacity)
        self.southeast = Quadtree(Rectangle(x + w, y + h, w, h), self.capacity)
        self.southwest = Quadtree(Rectangle(x - w, y + h, w, h), self.capacity)
        self.divided = True

    def insert(self, point):
        if not self.boundary.contains(point):
            return False
        if len(self.points) < self.capacity and not self.divided:
            self.points.append(point)
            return True
        if not self.divided:
            self.subdivide()
        return (self.northeast.insert(point) or self.northwest.insert(point) or
                self.southeast.insert(point) or self.southwest.insert(point))

    def query(self, range_rect, found=None):
        if found is None:
            found = []
        if not self.boundary.intersects(range_rect):
            return found
        for p in self.points:
            if range_rect.contains(p):
                found.append(p)
        if self.divided:
            self.northeast.query(range_rect, found)
            self.northwest.query(range_rect, found)
            self.southeast.query(range_rect, found)
            self.southwest.query(range_rect, found)
        return found


tree = Quadtree(Rectangle(50, 50, 50, 50))  # covers [0,100] x [0,100]
points = [(10,10),(15,15),(60,60),(62,65),(80,10),(20,80),(55,55),(58,52)]
for p in points:
    tree.insert(p)

found = tree.query(Rectangle(57, 57, 10, 10))  # region around (57, 57)
print(sorted(found))  # [(55,55), (58,52), (60,60), (62,65)]

#include <iostream>
#include <vector>
#include <memory>

struct Point { double x, y; };

struct Rectangle {
    double x, y, halfW, halfH; // center (x, y), half-width, half-height

    bool contains(const Point& p) const {
        return p.x >= x - halfW && p.x <= x + halfW &&
               p.y >= y - halfH && p.y <= y + halfH;
    }

    bool intersects(const Rectangle& other) const {
        return !(other.x - other.halfW > x + halfW ||
                 other.x + other.halfW < x - halfW ||
                 other.y - other.halfH > y + halfH ||
                 other.y + other.halfH < y - halfH);
    }
};

class Quadtree {
public:
    explicit Quadtree(Rectangle boundary, int capacity = 4)
        : boundary_(boundary), capacity_(capacity), divided_(false) {}

    bool insert(const Point& p) {
        if (!boundary_.contains(p)) return false;
        if (points_.size() < static_cast<size_t>(capacity_) && !divided_) {
            points_.push_back(p);
            return true;
        }
        if (!divided_) subdivide();
        return northeast_->insert(p) || northwest_->insert(p) ||
               southeast_->insert(p) || southwest_->insert(p);
    }

    void query(const Rectangle& range, std::vector<Point>& found) const {
        if (!boundary_.intersects(range)) return;
        for (const auto& p : points_) {
            if (range.contains(p)) found.push_back(p);
        }
        if (divided_) {
            northeast_->query(range, found);
            northwest_->query(range, found);
            southeast_->query(range, found);
            southwest_->query(range, found);
        }
    }

private:
    Rectangle boundary_;
    int capacity_;
    bool divided_;
    std::vector<Point> points_;
    std::unique_ptr<Quadtree> northeast_, northwest_, southeast_, southwest_;

    void subdivide() {
        double w = boundary_.halfW / 2, h = boundary_.halfH / 2;
        northeast_ = std::make_unique<Quadtree>(Rectangle{boundary_.x + w, boundary_.y - h, w, h}, capacity_);
        northwest_ = std::make_unique<Quadtree>(Rectangle{boundary_.x - w, boundary_.y - h, w, h}, capacity_);
        southeast_ = std::make_unique<Quadtree>(Rectangle{boundary_.x + w, boundary_.y + h, w, h}, capacity_);
        southwest_ = std::make_unique<Quadtree>(Rectangle{boundary_.x - w, boundary_.y + h, w, h}, capacity_);
        divided_ = true;
    }
};

int main() {
    Quadtree tree(Rectangle{50, 50, 50, 50}); // covers [0,100] x [0,100]

    std::vector<Point> points{{10,10},{15,15},{60,60},{62,65},{80,10},{20,80},{55,55},{58,52}};
    for (const auto& p : points) tree.insert(p);

    std::vector<Point> found;
    tree.query(Rectangle{57, 57, 10, 10}, found); // region around (57, 57)
    for (const auto& p : found) {
        std::cout << "(" << p.x << ", " << p.y << ") ";
    }
    std::cout << '\n';
}

import java.util.ArrayList;
import java.util.List;

public class Quadtree {
    static class Point {
        double x, y;
        Point(double x, double y) { this.x = x; this.y = y; }
        public String toString() { return "(" + x + ", " + y + ")"; }
    }

    static class Rectangle {
        double x, y, halfW, halfH; // center + half-dimensions

        Rectangle(double x, double y, double halfW, double halfH) {
            this.x = x; this.y = y; this.halfW = halfW; this.halfH = halfH;
        }

        boolean contains(Point p) {
            return p.x >= x - halfW && p.x <= x + halfW &&
                   p.y >= y - halfH && p.y <= y + halfH;
        }

        boolean intersects(Rectangle other) {
            return !(other.x - other.halfW > x + halfW ||
                      other.x + other.halfW < x - halfW ||
                      other.y - other.halfH > y + halfH ||
                      other.y + other.halfH < y - halfH);
        }
    }

    private final Rectangle boundary;
    private final int capacity;
    private final List<Point> points = new ArrayList<>();
    private boolean divided = false;
    private Quadtree northeast, northwest, southeast, southwest;

    Quadtree(Rectangle boundary, int capacity) {
        this.boundary = boundary;
        this.capacity = capacity;
    }

    boolean insert(Point p) {
        if (!boundary.contains(p)) return false;
        if (points.size() < capacity && !divided) {
            points.add(p);
            return true;
        }
        if (!divided) subdivide();
        return northeast.insert(p) || northwest.insert(p) ||
               southeast.insert(p) || southwest.insert(p);
    }

    void query(Rectangle range, List<Point> found) {
        if (!boundary.intersects(range)) return;
        for (Point p : points) {
            if (range.contains(p)) found.add(p);
        }
        if (divided) {
            northeast.query(range, found);
            northwest.query(range, found);
            southeast.query(range, found);
            southwest.query(range, found);
        }
    }

    private void subdivide() {
        double w = boundary.halfW / 2, h = boundary.halfH / 2;
        northeast = new Quadtree(new Rectangle(boundary.x + w, boundary.y - h, w, h), capacity);
        northwest = new Quadtree(new Rectangle(boundary.x - w, boundary.y - h, w, h), capacity);
        southeast = new Quadtree(new Rectangle(boundary.x + w, boundary.y + h, w, h), capacity);
        southwest = new Quadtree(new Rectangle(boundary.x - w, boundary.y + h, w, h), capacity);
        divided = true;
    }

    public static void main(String[] args) {
        Quadtree tree = new Quadtree(new Rectangle(50, 50, 50, 50), 4);
        double[][] raw = { {10,10},{15,15},{60,60},{62,65},{80,10},{20,80},{55,55},{58,52} };
        for (double[] xy : raw) tree.insert(new Point(xy[0], xy[1]));

        List<Point> found = new ArrayList<>();
        tree.query(new Rectangle(57, 57, 10, 10), found);
        System.out.println(found); // points near (57, 57)
    }
}

An Octree is the direct 3D generalization of a Quadtree: instead of splitting a square into four quadrants, it splits a cube into eight octants (adding a z-axis midpoint alongside x and y), recursing the same way until each octant holds few enough points. Octrees are the standard spatial index for 3D graphics, point-cloud processing, and voxel-based collision detection, for exactly the same reason Quadtrees work well in 2D: most of empty space gets pruned in one comparison per level.

7. R-Tree

Core insight: An R-Tree groups nearby objects using their bounding rectangles into a hierarchical tree of bounding boxes — each internal node's box is the smallest rectangle that encloses all of its children's boxes. A spatial query only needs to descend into a child whose bounding box overlaps the query region; anything whose box doesn't overlap is pruned along with everything it contains, no matter how many objects it holds.

Unlike the k-d Tree or Quadtree, an R-Tree indexes arbitrary shapes and rectangles — not just points — which is why it is the standard index used by GIS systems and spatial databases such as PostGIS for polygons, road segments, and other extended geometry. This lesson covers the R-Tree at the conceptual level only; a full implementation is not included here, since production R-Tree variants (R*-tree and others) depend on a node-splitting heuristic that decides how to divide an overflowing node's entries between two new bounding boxes while minimizing overlap and wasted area — a nontrivial optimization problem in its own right, well beyond what a short lesson section can responsibly cover.

The sketch below shows only the overlap-driven query idea — inserting new entries into a single, never-split node, and then walking the box hierarchy to answer an overlap query. It intentionally has no splitting logic and is not a usable R-Tree implementation on its own:

class BoundingBox:
    def __init__(self, min_x, min_y, max_x, max_y):
        self.min_x, self.min_y = min_x, min_y
        self.max_x, self.max_y = max_x, max_y

    def overlaps(self, other):
        return not (other.min_x > self.max_x or other.max_x < self.min_x or
                    other.min_y > self.max_y or other.max_y < self.min_y)

    def expand_to_include(self, other):
        return BoundingBox(min(self.min_x, other.min_x), min(self.min_y, other.min_y),
                            max(self.max_x, other.max_x), max(self.max_y, other.max_y))


class RTreeLeaf:
    def __init__(self, box, data):
        self.box, self.data = box, data


class RTreeNode:
    # NOTE: a real R-tree chooses the child needing the least box enlargement
    # and splits a node once it overflows, using an area- or overlap-minimizing
    # heuristic (quadratic split, R*-tree, ...). This sketch skips all of that
    # -- it exists only to show how an overlap query descends the box tree.
    def __init__(self):
        self.entries = []  # list of (box, RTreeLeaf)
        self.box = None

    def insert(self, box, data):
        self.entries.append((box, RTreeLeaf(box, data)))
        self.box = box if self.box is None else self.box.expand_to_include(box)

    def query(self, region):
        results = []
        if self.box is not None and not self.box.overlaps(region):
            return results
        for box, leaf in self.entries:
            if box.overlaps(region):
                results.append(leaf.data)
        return results

8. Complexity Comparison Table

Structure	Build Time	Query Time	Best For
Interval Tree	$O(n \log n)$	$O(\log n)$ for one overlap; $O(\log n + k)$ for all overlaps	Overlap detection, scheduling conflicts
Range Tree (1D)	$O(n \log n)$	$O(\log n + k)$	Static sorted 1D data, many repeated range lookups
k-d Tree	$O(n \log n)$	$O(\log n)$ average nearest-neighbor (worst case $O(n)$); range search roughly $O(\sqrt{n} + k)$ in 2D	Nearest-neighbor search, low-dimensional range search
Quadtree	$O(n \log n)$ average (depends on point distribution)	$O(\log n + k)$ average (degrades toward $O(n)$ if points cluster)	Uniform 2D partitioning, collision detection, spatial grids
R-Tree	$O(n \log n)$ (via repeated insert, or faster with bulk-loading)	$O(\log n + k)$ average (worst case $O(n)$ with heavy box overlap)	Indexing rectangles/polygons, GIS, spatial databases

9. Applications & Alternatives

Where each structure shows up in practice

Interval Tree: calendar and meeting-room conflict detection — does a proposed booking overlap any existing one?
k-d Tree: nearest-neighbor search — "find the closest restaurant to my current location," or the nearest point in a k-nearest-neighbors classifier.
Quadtree: game engines and collision detection — quickly narrow down which pairs of on-screen objects are even close enough to check for a collision.
R-Tree: GIS and mapping systems — indexing roads, building footprints, and other geometry so a map view only loads what's on screen.

As with the Fenwick and Segment Trees discussed earlier in this series, the right choice here is defined by the query shape, not by implementation simplicity: a sorted array with binary search answers 1D range queries in $O(\log n + k)$ with no extra structure at all when the data is static, but it cannot handle overlapping intervals or efficient updates the way an Interval Tree or Range Tree can.

10. Exercises

Easy

Given the intervals (1,3), (2,6), (8,10), (15,18), build an Interval Tree and use search_overlap to determine whether any two of them overlap. Which pair overlaps, and which single call finds it?

Medium

Using the k-d tree built in the hand-trace above — from (3,6), (17,15), (13,15), (6,12), (9,1), (2,7), (10,19) — find the nearest neighbor to the query point (11, 17), either by hand (compute each distance directly, then confirm with a trace of the recursive search) or by running the code above.

Hard

Extend the Quadtree code above to support efficient collision detection for many moving points: after each frame updates positions, query the quadtree with a small rectangle centered on each point to find its nearby neighbors cheaply, instead of comparing every pair of points. Discuss when to rebuild the quadtree from scratch each frame versus incrementally removing and reinserting only the points that moved.

Mastery challenge: A ride-sharing dispatch service must repeatedly answer "which driver is closest to this rider?" as thousands of drivers move every few seconds, and separately flag whenever two scheduled airport-shuttle bookings would use the same vehicle during an overlapping time window. Choose a structure for each sub-problem, justify the choice against the complexity table above, and explain what changes if driver positions update far more often than riders issue requests.

Review rhythm: tomorrow, reconstruct the Interval Tree's max_end pruning rule and the k-d Tree's pruning rule without notes; next week, implement the Quadtree range query in all three languages from memory; several weeks later, identify which of these five structures fits a new spatial or interval problem you encounter, and justify it against the alternatives in the comparison table.

11. Summary Cheat Sheet

Interval Tree: augmented BST keyed on interval start, each node stores the max endpoint in its subtree, prunes on overlap queries in $O(\log n)$.
Range Tree (1D): balanced BST over sorted points, splits at the split node into canonical subtrees, answers range queries in $O(\log n + k)$.
k-d Tree: alternates the splitting axis by depth, prunes nearest-neighbor search using the splitting-plane distance.
Quadtree: splits 2D space into four fixed quadrants by spatial midpoint (not by point position); Octree is its 3D generalization with eight children.
R-Tree: groups objects by bounding rectangle into a hierarchy of boxes, prunes any subtree whose box doesn't overlap the query region.
Fenwick/Segment Trees solve a different problem — range aggregates over a fixed sorted array index — not overlap or multi-dimensional region queries.
Choose by query shape: overlapping intervals, static 1D ranges, nearest neighbor, uniform spatial partitioning, or indexing extended shapes each point to a different structure above.

Cookie Consent

Interval, Range & Spatial Search Trees

Table of Contents

1. Introduction & Motivation

2. Prerequisites

3. Interval Tree

Hand-trace an overlap query

4. Range Tree (1D)

A balanced BST over sorted points

5. k-d Tree

Hand-trace building a k-d tree

6. Quadtree (and Octree)

7. R-Tree

8. Complexity Comparison Table

9. Applications & Alternatives

Where each structure shows up in practice

10. Exercises

Easy

Medium

Hard

11. Summary Cheat Sheet

Cookie Consent

Interval, Range & Spatial Search Trees

Table of Contents

1. Introduction & Motivation

2. Prerequisites

3. Interval Tree

Hand-trace an overlap query

4. Range Tree (1D)

A balanced BST over sorted points

5. k-d Tree

Hand-trace building a k-d tree

6. Quadtree (and Octree)

7. R-Tree

8. Complexity Comparison Table

9. Applications & Alternatives

Where each structure shows up in practice

10. Exercises

Easy

Medium

Hard

11. Summary Cheat Sheet

Continue the DSA Curriculum

Data Structures & Algorithms Hub

Part 10: BST & Balanced Trees

Union-Find, Trie, Fenwick Tree & Segment Tree