k-d Tree Search

k-d tree search organizes points in k-dimensional space using recursive axis aligned partitions. Each level splits the space along one coordinate axis.

It supports both exact membership queries and range or nearest neighbor search.

Problem

Given a set of points in k-dimensional space and a query point or region, find:

whether a point exists
or all points in a region
or the nearest neighbor

Structure

Each node stores:

field	meaning
point	k-dimensional point
axis	splitting dimension
left	points with smaller coordinate on axis
right	points with larger coordinate on axis

The splitting axis cycles:

axis = depth \bmod k

Exact Search Algorithm

Search follows binary tree logic using the splitting axis.

kd_search(node, target, depth):
    if node is null:
        return false

    if node.point == target:
        return true

    axis = depth mod k

    if target[axis] < node.point[axis]:
        return kd_search(node.left, target, depth + 1)
    else:
        return kd_search(node.right, target, depth + 1)

Range Search Algorithm

Collect all points inside a hyperrectangle.

kd_range_search(node, range, depth, result):
    if node is null:
        return

    if node.point inside range:
        add node.point to result

    axis = depth mod k

    if range.min[axis] <= node.point[axis]:
        kd_range_search(node.left, range, depth + 1, result)

    if node.point[axis] <= range.max[axis]:
        kd_range_search(node.right, range, depth + 1, result)

Example

2D points:

point
(2, 3)
(5, 4)
(9, 6)
(4, 7)
(8, 1)
(7, 2)

Tree splits:

depth 0: x axis
depth 1: y axis
depth 2: x axis

Search for point (5, 4):

step	axis	action
1	x	go right or left based on x
2	y	refine branch
3	match	found

Correctness

Each node partitions space into two half spaces along a selected axis. Every point in the left subtree satisfies:

p[axis] \le node[axis]

and every point in the right subtree satisfies:

p[axis] > node[axis]

This invariant ensures that at each step, the algorithm eliminates all regions that cannot contain the target or valid range points.

For exact search, the recursion follows the only branch that could contain the target. For range search, both branches are explored only when they may intersect the query region.

Thus all valid points are found and no invalid points are included.

Complexity

Let $n$ be number of points.

operation	average	worst
search	$O(\log n)$	$O(n)$
range query	$O(\log n + k)$	$O(n)$
nearest neighbor	$O(\log n)$ average	$O(n)$ worst

Space complexity:

O(n)

When to Use

k-d trees are useful when:

data is low to moderate dimensional (typically 2D to 10D)
spatial queries are frequent
nearest neighbor search is needed
dataset is not extremely high dimensional

Compared to range trees, k-d trees use less memory but have weaker worst case guarantees.

Implementation

class Node:
    def __init__(self, point, axis=0):
        self.point = point
        self.axis = axis
        self.left = None
        self.right = None

def kd_search(node, target, depth=0):
    if node is None:
        return False

    if node.point == target:
        return True

    axis = depth % len(target)

    if target[axis] < node.point[axis]:
        return kd_search(node.left, target, depth + 1)
    else:
        return kd_search(node.right, target, depth + 1)

type Point []int

type Node struct {
	Point Point
	Left  *Node
	Right *Node
}

func KdSearch(node *Node, target Point, depth int) bool {
	if node == nil {
		return false
	}

	match := true
	for i := range target {
		if node.Point[i] != target[i] {
			match = false
			break
		}
	}

	if match {
		return true
	}

	axis := depth % len(target)

	if target[axis] < node.Point[axis] {
		return KdSearch(node.Left, target, depth+1)
	}

	return KdSearch(node.Right, target, depth+1)
}