Introduction

Range search in a KD-tree means finding all points that fall inside a query rectangle or hyperrectangle. The key idea is not to visit every node. Instead, you use the splitting plane at each node to decide which subtrees can possibly intersect the query range.

That pruning logic is what makes a KD-tree useful. Without it, you are just doing a linear scan with extra overhead.

The Core Recursion Idea

At each node, you do two things:

1. check whether the node's point lies inside the query box
2. decide whether to recurse into the left subtree, right subtree, or both

The decision depends on the split axis.

If the node splits on axis axis and the query interval on that axis overlaps both sides of the split, you search both children. Otherwise, you search only the relevant side.

Python Example

1class Node:
2    def __init__(self, point, axis, left=None, right=None):
3        self.point = point
4        self.axis = axis
5        self.left = left
6        self.right = right
7
8
9def in_range(point, low, high):
10    return all(low[i] <= point[i] <= high[i] for i in range(len(point)))
11
12
13def range_search(node, low, high, result=None):
14    if result is None:
15        result = []
16    if node is None:
17        return result
18
19    if in_range(node.point, low, high):
20        result.append(node.point)
21
22    axis = node.axis
23    split_value = node.point[axis]
24
25    if low[axis] <= split_value:
26        range_search(node.left, low, high, result)
27    if high[axis] >= split_value:
28        range_search(node.right, low, high, result)
29
30    return result

This is the essential algorithm. The pruning happens in the last two conditional checks.

Why the Pruning Works

Suppose the current node splits the plane on the x-axis at x = 7.

• if the query box ends before x = 7, only the left subtree can contain matches
• if the query box starts after x = 7, only the right subtree can contain matches
• if the query box spans x = 7, both subtrees are relevant

The same logic works in higher dimensions by checking the current split axis only.

Small Example

Imagine a 2D query box with:

• lower corner (3, 2)
• upper corner (8, 6)

At a node splitting on x with point (5, 4), the point itself is inside the box, so it is reported.

Because the query interval on x spans from 3 to 8, both left and right children may still contain valid points, so both branches are searched.

This is a good example of how node inclusion and subtree pruning are related but separate decisions.

Complexity Perspective

In the average case, KD-tree range search can avoid visiting large parts of the tree. In the worst case, especially with bad tree balance or a very large query region, it can still approach linear time.

So the real performance gain depends on:

• tree balance
• point distribution
• dimensionality
• query-box size

KD-trees are most effective in relatively low dimensions. In high-dimensional spaces, pruning becomes less effective.

Common Pitfalls

The biggest mistake is forgetting that subtree pruning depends only on the current split axis, not on all coordinates at once.

Another common issue is using strict inequalities when the query should include boundary points. Decide clearly whether the range is inclusive or exclusive.

People also sometimes assume KD-trees remain efficient in very high dimensions. In practice, the advantage can degrade quickly.

Finally, range search quality depends on the tree being built sensibly. A badly unbalanced KD-tree undermines the whole point of the structure.

Summary

• Range search in a KD-tree reports points inside a query box.
• At each node, test the point itself and prune subtrees using the split axis.
• Search the left subtree if the query reaches the left side of the split.
• Search the right subtree if the query reaches the right side of the split.
• Efficiency depends on balance, dimensionality, and query size.
• The pruning logic is what makes KD-tree range search useful.