Dimensions
At depth 0 the tree compares x-coordinates, at depth 1 y-coordinates, then x again. The axis stored at a node determines both the search comparison and the split line drawn through that point.
Data Structures algorithms / interactive lesson
KD Tree
Build a two-dimensional KD tree while the matching plane partition shows alternating X and Y split dimensions.
University
Guided lesson
2D spatial search tree
KD tree
2D planeactive axis: X
Binary tree viewX verticalY horizontal
About the algorithm
A KD tree is a binary search tree for k-dimensional points. In two dimensions it alternates x and y comparisons, creating a recursive partition of the plane.
Spatial partition
Every node owns a rectangular region. An x-split divides it vertically, while a y-split divides it horizontally. Children inherit only their side of the parent's region.
Queries
KD trees support range search and nearest-neighbor search by pruning regions that cannot contain useful answers. The quality depends on how balanced the partition is.
Code companion
Connect each visual decision to an implementation pattern.
insert(node, point, depth):
axis = depth mod k
if node is empty:
return new Node(point, axis)
if point[axis] < node.point[axis]:
node.left = insert(node.left, point, depth + 1)
else:
node.right = insert(node.right, point, depth + 1)
return node