### Subtree Traversal Example

Source: https://github.com/kristofferc/nearestneighbors.jl/blob/master/README.md

Shows how to traverse a specific subtree starting from any node. This example iterates only through the leaves of the left subtree.

```julia
# Walk only the left subtree
left_child, _ = children(treeroot(tree))
for node in Leaves(left_child)
    # Only visits leaves under left_child
    pts = leafpoints(node)
    println("Leaf with ", length(pts), " points")
end
```

--------------------------------

### Parent Traversal Example

Source: https://github.com/kristofferc/nearestneighbors.jl/blob/master/README.md

Demonstrates navigating up the tree structure using the `parent` function. This example verifies that the parent of a child node is indeed the root node.

```julia
tree = KDTree(rand(3, 100))
root = treeroot(tree)
left_child, right_child = children(root)

# Walk back up to root
@assert isroot(root)
@assert !isroot(left_child)

parent_node = parent(left_child)
@assert isroot(parent_node)
@assert treeregion(parent_node) == treeregion(root)
```

--------------------------------

### Periodic KDTree Query

Source: https://github.com/kristofferc/nearestneighbors.jl/blob/master/README.md

Demonstrates querying a KDTree with periodic boundary conditions. The example shows how a query near an x-boundary correctly identifies a wrapped neighbor.

```julia
# 2D domain: x-periodic, y-infinite
data = [SVector(1.0, 2.0), SVector(9.0, 8.0)]
kdtree = KDTree(data)
ptree = PeriodicTree(kdtree, [0.0, 0.0], [10.0, Inf])

# Query near x-boundary finds wrapped neighbor
query = [0.5, 3.0]
idxs, dists = knn(ptree, query, 1)
# Finds data[1] with wrapped x-distance of 0.5 instead of 8.5
```

--------------------------------

### Subtree Traversal with AbstractTrees

Source: https://context7.com/kristofferc/nearestneighbors.jl/llms.txt

Performs a traversal (e.g., iterating over leaves) within a specific subtree using AbstractTrees.jl. This example shows visiting only leaves under the `left_child`.

```julia
for node in Leaves(left_child)
    # Only visits leaves under left_child
end
```

--------------------------------

### Initialize NearestNeighbors Environment

Source: https://github.com/kristofferc/nearestneighbors.jl/blob/master/examples/balltree_illustration.ipynb

Imports necessary packages and sets the global plotting theme to dark mode.

```julia
using NearestNeighbors
using Colors
using CairoMakie
using AbstractTrees
using StableRNGs
import NearestNeighbors.HyperSphere
import NearestNeighbors: treeroot, leafpoints, treeregion

set_theme!(theme_dark())
```

--------------------------------

### Navigating Tree Structure with AbstractTrees

Source: https://context7.com/kristofferc/nearestneighbors.jl/llms.txt

Demonstrates basic tree navigation using AbstractTrees.jl, including accessing children, checking for the root node, and retrieving the parent node.

```julia
left_child, right_child = children(root)
@assert isroot(root)
@assert !isroot(left_child)
parent_node = parent(left_child)
@assert treeregion(parent_node) == treeregion(root)
```

--------------------------------

### Initialize a KD tree

Source: https://github.com/kristofferc/nearestneighbors.jl/blob/master/examples/kdtree_illustration.ipynb

Create a KD tree using random data points with a specified leaf size.

```julia
rng = StableRNG(42)
tree = KDTree(randn(rng, 2, 500), Euclidean(); leafsize = 50)
```

--------------------------------

### Creating DataFreeTree for Large Datasets

Source: https://context7.com/kristofferc/nearestneighbors.jl/llms.txt

Demonstrates creating a `DataFreeTree` for large, on-disk datasets that exceed available RAM. It stores only the tree structure and requires re-linking data later.

```julia
using NearestNeighbors
using Mmap

# For very large on-disk datasets
ndim = 3
npoints = 10_000_000

# Memory-map the data file
datafilename = "large_dataset.bin"
data = Mmap.mmap(datafilename, Matrix{Float32}, (ndim, npoints))

# Create a DataFreeTree (stores only tree structure, not data)
dftree = DataFreeTree(KDTree, data)
```

--------------------------------

### Create PeriodicTree for Periodic Boundary Conditions

Source: https://github.com/kristofferc/nearestneighbors.jl/blob/master/README.md

Wraps an existing tree (KDTree, BallTree, or BruteTree) to handle nearest neighbor searches with periodic boundary conditions. Requires specifying the minimum and maximum bounds for each dimension.

```julia
using NearestNeighbors, StaticArrays

# Create data in a 2D periodic domain
data = [SVector(0.1, 0.2), SVector(0.8, 0.9), SVector(0.5, 0.5)]
kdtree = KDTree(data)

# Create periodic tree with bounds [0,1] × [0,1]
ptree = PeriodicTree(kdtree, [0.0, 0.0], [1.0, 1.0])
```

--------------------------------

### Import dependencies for NearestNeighbors.jl

Source: https://github.com/kristofferc/nearestneighbors.jl/blob/master/examples/kdtree_illustration.ipynb

Load the necessary packages for tree construction, color handling, plotting, and tree traversal.

```julia
using NearestNeighbors
using Colors
using CairoMakie
using AbstractTrees
using StableRNGs
```

--------------------------------

### Parallel Tree Building in NearestNeighbors.jl

Source: https://github.com/kristofferc/nearestneighbors.jl/blob/master/README.md

Illustrates how KDTree and BallTree can be built in parallel using multiple threads for performance gains on large datasets. Parallel building is enabled by default when multiple threads are available.

```julia
# Parallel by default when multiple threads available
kdtree = KDTree(data)
balltree = BallTree(data)

# Explicitly disable parallel building
kdtree_seq = KDTree(data; parallel=false)
```

--------------------------------

### Create Nearest Neighbor Trees in Julia

Source: https://github.com/kristofferc/nearestneighbors.jl/blob/master/README.md

Demonstrates the creation of different types of nearest neighbor trees: KDTree, BallTree, BruteTree, and PeriodicTree. Specify data, metric, and optional parameters like leafsize and reorder.

```julia
using NearestNeighbors
data = rand(3, 10^4)

# Create trees
kdtree = KDTree(data; leafsize = 25)
balltree = BallTree(data, Minkowski(3.5); reorder = false)
brutetree = BruteTree(data)
periodictree = PeriodicTree(kdtree, [0.0, 0.0, 0.0], [1.0, 1.0, 1.0])
```

--------------------------------

### Create a BruteTree

Source: https://context7.com/kristofferc/nearestneighbors.jl/llms.txt

Construct a BruteTree for exhaustive linear search. Useful for small datasets or unsupported metrics.

```julia
using NearestNeighbors
using Distances

# Create small dataset
data = rand(3, 100)

# Basic BruteTree
brutetree = BruteTree(data)

# BruteTree with custom metric (supports any PreMetric)
brutetree = BruteTree(data, Euclidean())
brutetree_cosine = BruteTree(data, CosineDist())

# Note: leafsize and reorder parameters are ignored for BruteTree
brutetree = BruteTree(data; leafsize=10, reorder=true)  # Parameters ignored
```

--------------------------------

### Create a PeriodicTree

Source: https://context7.com/kristofferc/nearestneighbors.jl/llms.txt

Wrap a tree structure to handle periodic boundary conditions. Use Inf for non-periodic dimensions.

```julia
using NearestNeighbors
using StaticArrays

# Create data in a 3D periodic box [0,1]^3
data = [SVector(rand(3)...) for _ in 1:1000]
bounds_min = [0.0, 0.0, 0.0]
bounds_max = [1.0, 1.0, 1.0]

# Create periodic tree wrapping a KDTree
kdtree = KDTree(data)
ptree = PeriodicTree(kdtree, bounds_min, bounds_max)

# Query near boundary - finds neighbors through periodic wrapping
query_point = [0.05, 0.05, 0.05]
idxs, dists = knn(ptree, query_point, 5)

# Mixed periodic/non-periodic dimensions (use Inf for non-periodic)
data_2d = [SVector(rand(2)...) for _ in 1:500]
kdtree_2d = KDTree(data_2d)
# x-periodic [0,10], y-infinite
ptree_mixed = PeriodicTree(kdtree_2d, [0.0, -Inf], [10.0, Inf])

# Works with BallTree and BruteTree too
balltree = BallTree(data)
ptree_ball = PeriodicTree(balltree, bounds_min, bounds_max)
```

--------------------------------

### Injecting Data into DataFreeTree

Source: https://github.com/kristofferc/nearestneighbors.jl/blob/master/README.md

Demonstrates how to re-link a DataFreeTree to its data source for performing operations. This allows look-ups and other tree operations on the on-disk data.

```julia
tree = injectdata(dftree, data) # yields a KDTree
knn(tree, data[:,1], 3) # perform operations as usual
```

--------------------------------

### Create a KDTree

Source: https://context7.com/kristofferc/nearestneighbors.jl/llms.txt

Construct a KDTree for low-dimensional data. Supports axis-aligned metrics and parallel construction.

```julia
using NearestNeighbors

# Create data: 3D points as a matrix (dimensions × points)
data = rand(3, 10_000)

# Basic KDTree with default Euclidean metric
kdtree = KDTree(data)

# KDTree with custom parameters
kdtree = KDTree(data;
    leafsize = 25,      # Points per leaf node (default: 25)
    reorder = true,     # Reorder data for cache locality (default: true)
    parallel = true     # Parallel construction (default: Threads.nthreads() > 1)
)

# KDTree with different metric
using Distances
kdtree_chebyshev = KDTree(data, Chebyshev())
kdtree_minkowski = KDTree(data, Minkowski(3.5))
kdtree_cityblock = KDTree(data, Cityblock())

# Using vector of StaticArrays (more efficient)
using StaticArrays
data_svec = [SVector{3, Float64}(rand(3)...) for _ in 1:10_000]
kdtree_svec = KDTree(data_svec)

# Disable parallel construction
kdtree_seq = KDTree(data; parallel=false)
```

--------------------------------

### DataFreeTree Construction

Source: https://github.com/kristofferc/nearestneighbors.jl/blob/master/README.md

Shows how to construct a DataFreeTree for large, on-disk datasets. This tree stores indexing structures without the actual data, saving memory.

```julia
using Mmap
dim = 2
ndata = 10_000_000_000
data = Mmap.mmap(datafilename, Matrix{Float32}, (ndim, ndata))
data[:] = rand(Float32, ndim, ndata) # create example data
dftree = DataFreeTree(KDTree, data)
```

--------------------------------

### Periodic Boundary Conditions

Source: https://github.com/kristofferc/nearestneighbors.jl/blob/master/README.md

Provides nearest neighbor searches with periodic boundary conditions using `PeriodicTree`.

```APIDOC
## Periodic Boundary Conditions

The `PeriodicTree` provides nearest neighbor searches with periodic boundary conditions. It reuses an internal deduplication buffer, so the same `PeriodicTree` instance should not be queried concurrently from multiple threads without external synchronization.

### Creating a PeriodicTree

A `PeriodicTree` wraps an existing tree (`KDTree`, `BallTree`, or `BruteTree`) and handles periodic boundary conditions:

```julia
PeriodicTree(tree, bounds_min, bounds_max)
```

* `tree`: An existing tree built from your data
* `bounds_min`: Vector of minimum bounds for each dimension
* `bounds_max`: Vector of maximum bounds for each dimension (use `Inf` for non-periodic dimensions)

### Request Example

**Basic periodic boundaries:**
```julia
using NearestNeighbors, StaticArrays

# Create data in a 2D periodic domain
data = [SVector(0.1, 0.2), SVector(0.8, 0.9), SVector(0.5, 0.5)]
kdtree = KDTree(data)

# Create periodic tree with bounds [0,1] × [0,1]
ptree = PeriodicTree(kdtree, [0.0, 0.0], [1.0, 1.0])

# Query near boundary - finds neighbors through periodic wrapping
query_point = [0.05, 0.15]  # Near data[1] = [0.1, 0.2]
neighbor_point = [0.95, 0.85] # Near data[2] = [0.8, 0.9] via wrapping

idxs, dists = knn(ptree, query_point, 2)
println(idxs)
println(dists)
```

### Response Example

```julia
# Example output for knn query with PeriodicTree:
# ([1, 2], [0.05, 0.15])
# The indices correspond to the nearest neighbors considering periodic boundaries.
```
```

--------------------------------

### Re-linking Data to DataFreeTree

Source: https://context7.com/kristofferc/nearestneighbors.jl/llms.txt

Shows how to re-link memory-mapped data to a `DataFreeTree` to reconstruct a usable tree (e.g., KDTree) for performing queries.

```julia
using NearestNeighbors
using Mmap

# Assume dftree is already created as in the previous example
# data = Mmap.mmap(...)

# The dftree can be serialized/stored without the data
# Later, re-link to perform queries:
tree = injectdata(dftree, data)  # Returns a KDTree

# Perform queries as usual
idxs, dists = knn(tree, data[:, 1], 5)
```

--------------------------------

### Visualize progressive tree splitting by depth

Source: https://github.com/kristofferc/nearestneighbors.jl/blob/master/examples/kdtree_illustration.ipynb

Calculate node depths and visualize the active regions of the KD tree across multiple depth levels.

```julia
function node_depth(node)
    depth = 0
    current = node
    while !isnothing(AbstractTrees.parent(current))
        current = AbstractTrees.parent(current)
        depth += 1
    end
    return depth
end

# Collect all nodes with their depths
root = treeroot(tree)
all_nodes = collect(PreOrderDFS(root))
node_depths = [node_depth(node) for node in all_nodes]
max_depth = maximum(node_depths)

# For each depth level, get all "active" regions
# (nodes at that depth, or leaves from shallower depths)
function get_active_regions_at_depth(max_depth_to_show)
    active = []
    for (node, depth) in zip(all_nodes, node_depths)
        is_leaf = isempty(children(node))
        if depth == max_depth_to_show || (is_leaf && depth < max_depth_to_show)
            push!(active, node)
        end
    end
    return active
end

# Create figure with 2x3 grid of subplots
n_depths = min(max_depth + 1, 6)  # Show up to 6 depth levels
fig = Figure(backgroundcolor=:gray15, size=(900, 600), title="Foo")

for depth in 0:(n_depths-1)
    active_regions = get_active_regions_at_depth(depth)
    row = div(depth, 3) + 1
    col = mod(depth, 3) + 1
    ax = Axis(fig[row, col], aspect=DataAspect(), 
              title="Depth $depth ($(length(active_regions)) regions)",
              backgroundcolor=:gray20)
    
    # Draw all active regions at this depth
    for (i, node) in enumerate(active_regions)
        add_rectangle(ax, treeregion(node), RGB(1.0, 0.5, 1.0))
    end
end

fig
```

--------------------------------

### AbstractTrees.jl Tree Traversal

Source: https://github.com/kristofferc/nearestneighbors.jl/blob/master/README.md

Illustrates tree traversal using the AbstractTrees.jl interface. This includes pre-order, post-order, and leaf-only traversals, as well as accessing leaf points and their original data indices.

```julia
using NearestNeighbors
using AbstractTrees: PreOrderDFS, PostOrderDFS, Leaves, children, parent, isroot

tree = BallTree(rand(2, 100))
root = treeroot(tree)

# Pre-order walk over every node
for node in PreOrderDFS(root)
    region = treeregion(node)              # HyperSphere for BallTree
    if isempty(children(node))
        pts = leafpoints(node)             # zero-copy view of points in the leaf
        @info "Leaf" npoints = length(pts) radius = region.r
    end
end

# Only visit leaves
leaf_nodes = collect(Leaves(root))

# Pull original data indices stored in a leaf
first_leaf = first(leaf_nodes)
idxs_in_data = leaf_point_indices(first_leaf)
```

--------------------------------

### Pre-order Traversal with AbstractTrees

Source: https://context7.com/kristofferc/nearestneighbors.jl/llms.txt

Iterates through the tree nodes in a pre-order fashion (parent before children) using AbstractTrees.jl integration. Useful for inspecting tree structure and node properties.

```julia
for node in PreOrderDFS(root)
    region = treeregion(node)  # HyperSphere for BallTree
    if isempty(children(node))
        pts = leafpoints(node)  # Zero-copy view of points in leaf
        println("Leaf with $(length(pts)) points, radius=$(region.r)")
    else
        println("Internal node, radius=$(region.r)")
    end
end
```

--------------------------------

### Optimized Pre-order Traversal for KDTree

Source: https://context7.com/kristofferc/nearestneighbors.jl/llms.txt

A performance-optimized pre-order traversal for KDTree, avoiding AbstractTrees overhead. Use this for faster tree analysis when maximum performance is required.

```julia
using NearestNeighbors

data = rand(3, 10_000)
kdtree = KDTree(data)

# Pre-order traversal (faster than AbstractTrees.PreOrderDFS)
for node in preorder(kdtree)
    # Process node
end
```

--------------------------------

### Inspect Spatial Regions (BallTree)

Source: https://github.com/kristofferc/nearestneighbors.jl/blob/master/README.md

Demonstrates inspecting the spatial regions of nodes in a BallTree. It identifies leaf and internal nodes and prints their center and radius.

```julia
balltree = BallTree(rand(2, 100))
root = treeroot(balltree)
for node in PostOrderDFS(root)
    sphere = treeregion(node)  # HyperSphere
    isleaf = isempty(children(node))
    println(isleaf ? "Leaf" : "Internal", " node: center=", sphere.center, ", radius=", sphere.r)
end
```

--------------------------------

### Performance-Optimized Tree Walkers

Source: https://github.com/kristofferc/nearestneighbors.jl/blob/master/README.md

Provides custom, performance-optimized walkers for tree traversal. These include pre-order, post-order, and direct leaf iteration, offering higher efficiency than generic AbstractTrees walkers.

```julia
using NearestNeighbors

tree = KDTree(rand(3, 10000))

# Pre-order traversal (faster than AbstractTrees.PreOrderDFS)
for node in preorder(tree)
    # node is a TreeNode
end

# Post-order traversal
for node in postorder(tree)
    # process children before parent
end

# Direct leaf iteration (fastest for leaf-only access)
for node in leaves(tree)
    pts = leafpoints(node)
    # process leaf points
end
```

--------------------------------

### Tree Traversal with AbstractTrees Interface

Source: https://context7.com/kristofferc/nearestneighbors.jl/llms.txt

NearestNeighbors.jl implements the AbstractTrees.jl interface for KDTree and BallTree, enabling standard tree traversal and visualization using functions like `treeroot`, `children`, `parent`, and `isroot`.

```julia
using NearestNeighbors
using AbstractTrees: PreOrderDFS, PostOrderDFS, Leaves, children, parent, isroot

data = rand(2, 100)
balltree = BallTree(data)

# Get the root node
root = treeroot(balltree)
```

--------------------------------

### DataFreeTree with BallTree and Custom Metric

Source: https://context7.com/kristofferc/nearestneighbors.jl/llms.txt

Illustrates creating a `DataFreeTree` using `BallTree` and specifying a custom distance metric (Minkowski with p=3.0) for handling large datasets.

```julia
using NearestNeighbors
using Mmap
using Distances

# Assume data is memory-mapped as before
# data = Mmap.mmap(...)

# Works with BallTree too
dftree_ball = DataFreeTree(BallTree, data)
tree_ball = injectdata(dftree_ball, data)

# With custom metric
dftree_metric = DataFreeTree(BallTree, data, Minkowski(3.0))
```

--------------------------------

### Inspect Spatial Regions (KDTree)

Source: https://github.com/kristofferc/nearestneighbors.jl/blob/master/README.md

Illustrates how to inspect the spatial regions covered by nodes in a KDTree. It prints whether a node is a leaf or internal and its bounding rectangle coordinates.

```julia
kdtree = KDTree(rand(2, 100))
root = treeroot(kdtree)
for node in PreOrderDFS(root)
    rect = treeregion(node)  # HyperRectangle
    isleaf = isempty(children(node))
    println(isleaf ? "Leaf" : "Internal", " node covers:")
    println("  X: [", rect.mins[1], ", ", rect.maxes[1], "]")
    println("  Y: [", rect.mins[2], ", ", rect.maxes[2], "]")
end
```

--------------------------------

### Optimized Post-order Traversal for KDTree

Source: https://context7.com/kristofferc/nearestneighbors.jl/llms.txt

A performance-optimized post-order traversal for KDTree, processing children before the parent. This custom walker offers better performance than the AbstractTrees version.

```julia
using NearestNeighbors

data = rand(3, 10_000)
kdtree = KDTree(data)

# Post-order traversal (children before parent)
for node in postorder(kdtree)
    # Process children before parent
end
```

--------------------------------

### Visualize Tree Hierarchy

Source: https://github.com/kristofferc/nearestneighbors.jl/blob/master/examples/balltree_illustration.ipynb

Visualizes all nodes in the tree hierarchy using a plasma color gradient.

```julia
root = treeroot(tree)
n_nodes = length(collect(PreOrderDFS(root)))
cols = cgrad(:plasma, n_nodes, categorical=true)

fig = CairoMakie.Figure(backgroundcolor=:gray15)
ax = Axis(fig[1, 1], aspect = DataAspect(), title = "All nodes in tree hierarchy",
          backgroundcolor=:gray20)

for (i, node) in enumerate(PreOrderDFS(root))
    add_sphere(ax, treeregion(node), cols[i])
end

fig
```

--------------------------------

### Create a BallTree

Source: https://github.com/kristofferc/nearestneighbors.jl/blob/master/examples/balltree_illustration.ipynb

Generates a BallTree using random data points with a fixed seed for reproducibility.

```julia
rng = StableRNG(42)
tree = BallTree(rand(rng, 2, 100), Euclidean(); leafsize = 10)
```

--------------------------------

### Create a BallTree

Source: https://context7.com/kristofferc/nearestneighbors.jl/llms.txt

Construct a BallTree for high-dimensional data. Compatible with any metric from Distances.jl.

```julia
using NearestNeighbors
using Distances

# Create data
data = rand(10, 5_000)  # 10-dimensional data

# Basic BallTree with Euclidean metric
balltree = BallTree(data)

# BallTree with Minkowski metric
balltree = BallTree(data, Minkowski(3.5);
    leafsize = 25,
    reorder = true,
    parallel = true
)

# BallTree works with any Metric
balltree_hamming = BallTree(data, Hamming())
balltree_weighted = BallTree(data, WeightedEuclidean(rand(10)))
balltree_mahal = BallTree(data, Mahalanobis(rand(10, 10)))

# Using StaticArrays
using StaticArrays
data_svec = [SVector{10, Float64}(rand(10)...) for _ in 1:5_000]
balltree_svec = BallTree(data_svec)
```

--------------------------------

### Post-order Traversal with AbstractTrees

Source: https://context7.com/kristofferc/nearestneighbors.jl/llms.txt

Iterates through the tree nodes in a post-order fashion (children before parent) using AbstractTrees.jl integration. Useful for processing child nodes before their parent.

```julia
for node in PostOrderDFS(root)
    # Process children before parent
end
```

--------------------------------

### Visualize KD tree leaf nodes

Source: https://github.com/kristofferc/nearestneighbors.jl/blob/master/examples/kdtree_illustration.ipynb

Traverse the tree to extract leaf nodes and plot their regions and contained points using CairoMakie.

```julia
import NearestNeighbors.HyperRectangle
import NearestNeighbors: treeroot, leafpoints, treeregion

set_theme!(theme_dark())

# Adds a rectangle to an axis
function add_rectangle(ax, hr::HyperRectangle, color)
    x_min, x_max = hr.mins[1], hr.maxes[1]
    y_min, y_max = hr.mins[2], hr.maxes[2]
    lines!(ax, [x_min, x_max, x_max, x_min, x_min], [y_min, y_min, y_max, y_max, y_min]; color, linewidth=2)
end

# Iterate over the leaf nodes with the public traversal API
root = treeroot(tree)
leaf_nodes = collect(Leaves(root))
cols = Makie.wong_colors()

fig = CairoMakie.Figure(backgroundcolor=:gray15)
ax = Axis(fig[1, 1], aspect = DataAspect(), title = "Leaf nodes with their corresponding points",
          backgroundcolor=:gray20)

for (i, node) in enumerate(leaf_nodes)
    pts = leafpoints(node)
    col = cols[mod1(i, length(cols))]
    scatter!(ax, getindex.(pts, 1), getindex.(pts, 2); markersize=8, color=col)
    add_rectangle(ax, treeregion(node), col)
end

fig
```

--------------------------------

### Collect All Points in a Subtree

Source: https://github.com/kristofferc/nearestneighbors.jl/blob/master/README.md

Demonstrates collecting all points contained within a specific subtree. This is achieved by iterating through the leaves of the subtree and gathering their points.

```julia
# Get all points under a specific node
left_child, _ = children(treeroot(tree))
subtree_points = [pt for leaf in Leaves(left_child)
                     for pt in leafpoints(leaf)]
```

--------------------------------

### Perform kNN Search with PeriodicTree

Source: https://github.com/kristofferc/nearestneighbors.jl/blob/master/README.md

Queries a PeriodicTree to find nearest neighbors, automatically accounting for periodic boundary conditions. This is useful for simulations or data where points wrap around boundaries.

```julia
# Query near boundary - finds neighbors through periodic wrapping
query_point = [0.05, 0.15]  # Near data[1] = [0.1, 0.2]
neighbor_point = [0.95, 0.85] # Near data[2] = [0.8, 0.9] via wrapping

idxs, dists = knn(ptree, query_point, 2)
```

--------------------------------

### k-Nearest Neighbor (kNN) Searches

Source: https://github.com/kristofferc/nearestneighbors.jl/blob/master/README.md

Finds the `k` nearest neighbors to a given point or points.

```APIDOC
## k-Nearest Neighbor (kNN) Searches

A kNN search finds the `k` nearest neighbors to a given point or points. This is done with the methods:

```julia
knn(tree, point[s], k [, skip=Returns(false)]) -> idxs, dists
knn!(idxs, dists, tree, point, k [, skip=Returns(false)])
allknn(tree, k [, skip=Returns(false)]) -> idxs, dists
```

* `tree`: The tree instance.
* `point[s]`: A vector or matrix of points to find the `k` nearest neighbors for. A vector of numbers represents a single point; a matrix means the `k` nearest neighbors for each point (column) will be computed. `points` can also be a vector of vectors.
* `k`: Number of nearest neighbors to find.
* `skip` (optional): A predicate function to skip certain points, e.g., points already visited.
* `allknn`: Finds the `k` nearest neighbors for every point stored in the tree itself, automatically excluding the point being queried.

For the single closest neighbor, you can use `nn`:

```julia
nn(tree, point[s] [, skip=Returns(false)]) -> idx, dist
allnn(tree [, skip=Returns(false)]) -> idxs, dists
```

### Request Example

```julia
using NearestNeighbors
data = rand(3, 10^4)
k = 3
point = rand(3)

kdtree = KDTree(data)
idxs, dists = knn(kdtree, point, k)

println(idxs)
println(dists)

# Multiple points
points = rand(3, 4)
idxs, dists = knn(kdtree, points, k)

println(idxs)
println(dists)

# Static vectors
using StaticArrays
v = @SVector[0.5, 0.3, 0.2];

idxs, dists = knn(kdtree, v, k)

println(idxs)
println(dists)

# Preallocating input results
idxs, dists = zeros(Int32, k), zeros(Float32, k)
knn!(idxs, dists, kdtree, v, k)
```

### Response Example

```julia
# For single point query:
# 3-element Array{Int64,1}:
#  4683
#  6119
#  3278
#
# 3-element Array{Float64,1}:
#  0.039032201026256215
#  0.04134193711411951
#  0.042974090446474184

# For multiple points query:
# 4-element Array{Array{Int64,1},1}:
#  [3330, 4072, 2696]
#  [1825, 7799, 8358]
#  [3497, 2169, 3737]
#  [1845, 9796, 2908]
#
# 4-element Array{Array{Float64,1},1}:
#  [0.0298932, 0.0327349, 0.0365979]
#  [0.0348751, 0.0498355, 0.0506802]
#  [0.0318547, 0.037291, 0.0421208]
#  [0.03321, 0.0360935, 0.0411951]

# For static vector query:
# 3-element Array{Int64,1}:
#   842
#  3075
#  3046
#
# 3-element Array{Float64,1}:
#  0.04178677766255837
#  0.04556078331418939
#  0.049967238112417205

```

--------------------------------

### Perform kNN Search with Preallocated Results

Source: https://github.com/kristofferc/nearestneighbors.jl/blob/master/README.md

Performs a kNN search and stores the results in preallocated index and distance arrays. This can be more efficient for repeated searches with the same k value.

```julia
# Preallocating input results
idxs, dists = zeros(Int32, k), zeros(Float32, k)
knn!(idxs, dists, kdtree, v, k)
```

--------------------------------

### Perform kNN Search with KDTree

Source: https://github.com/kristofferc/nearestneighbors.jl/blob/master/README.md

Finds the k nearest neighbors to a given point or points using a KDTree. Ensure NearestNeighbors.jl is imported. Data can be a vector of numbers for a single point or a matrix for multiple points.

```julia
using NearestNeighbors
data = rand(3, 10^4)
k = 3
point = rand(3)

kdtree = KDTree(data)
idxs, dists = knn(kdtree, point, k)
```

```julia
# Multiple points
points = rand(3, 4)
idxs, dists = knn(kdtree, points, k)
```

```julia
# Static vectors
using StaticArrays
v = @SVector[0.5, 0.3, 0.2];

idxs, dists = knn(kdtree, v, k)
```

--------------------------------

### All-Points kNN Search with allknn

Source: https://context7.com/kristofferc/nearestneighbors.jl/llms.txt

Finds the k nearest neighbors for every point in the tree, automatically excluding the query point itself. Supports sorting results and skipping points with a predicate.

```julia
using NearestNeighbors

data = rand(3, 1000)
kdtree = KDTree(data)

# Find k nearest neighbors for every point in the tree
k = 5
idxs, dists = allknn(kdtree, k)
# idxs: Vector of 1000 vectors, each with k neighbor indices
# dists: Vector of 1000 vectors, each with k distances

# Sort results by distance
idxs, dists = allknn(kdtree, k, true)  # sortres=true

# With skip predicate
skip_func = i -> i > 500  # Skip points with index > 500
idxs, dists = allknn(kdtree, k, false, skip_func)
```

--------------------------------

### kNN Search with KDTree

Source: https://context7.com/kristofferc/nearestneighbors.jl/llms.txt

Performs k-nearest neighbors search on a KDTree. Supports single point, multiple points (matrix or vector of vectors), sorting results, and skipping points with a predicate function. Pre-allocated search with `knn!` is available to avoid allocations.

```julia
using NearestNeighbors

data = rand(3, 10_000)
kdtree = KDTree(data)
k = 5

# Single point query
point = rand(3)
idxs, dists = knn(kdtree, point, k)
# idxs: [4683, 6119, 3278, 7891, 2345]  (5 nearest neighbor indices)
# dists: [0.039, 0.041, 0.043, 0.048, 0.051]  (corresponding distances)

# Multiple points query (matrix: dims × num_points)
points = rand(3, 100)
idxs, dists = knn(kdtree, points, k)
# idxs: Vector of 100 vectors, each with k indices
# dists: Vector of 100 vectors, each with k distances

# Vector of vectors query
points_vec = [SVector{3}(rand(3)...) for _ in 1:50]
idxs, dists = knn(kdtree, points_vec, k)

# Sort results by distance (default is heap order)
idxs, dists = knn(kdtree, point, k, true)  # sortres=true

# Skip certain points using a predicate function
skip_func = i -> i in [1, 2, 3]  # Skip points 1, 2, 3
idxs, dists = knn(kdtree, point, k, false, skip_func)

# Pre-allocated search with knn! (avoids allocations)
idxs_buf = zeros(Int, k)
dists_buf = zeros(Float64, k)
knn!(idxs_buf, dists_buf, kdtree, point, k)
```

--------------------------------

### Direct Leaf Iteration for KDTree

Source: https://context7.com/kristofferc/nearestneighbors.jl/llms.txt

The fastest method for accessing only leaf nodes in a KDTree. It directly iterates over leaves, retrieving points for processing.

```julia
using NearestNeighbors

data = rand(3, 10_000)
kdtree = KDTree(data)

# Direct leaf iteration (fastest for leaf-only access)
total_points = 0
for node in leaves(kdtree)
    pts = leafpoints(node)
    total_points += length(pts)
end
println("Total points across all leaves: $total_points")
```

--------------------------------

### Perform k-Nearest Neighbor Search

Source: https://context7.com/kristofferc/nearestneighbors.jl/llms.txt

Use the knn function to retrieve indices and distances of the k nearest neighbors.

```julia
using NearestNeighbors
using StaticArrays

data = rand(3, 10_000)
kdtree = KDTree(data)

# Single point query
point = rand(3)
k = 5
idxs, dists = knn(kdtree, point, k)
```

--------------------------------

### Single Nearest Neighbor Search (nn)

Source: https://context7.com/kristofferc/nearestneighbors.jl/llms.txt

Convenience wrapper for finding the single nearest neighbor to a point.

```APIDOC
## nn(tree, point, [skip_func])

### Description
Finds the single nearest neighbor for a query point or set of points.

### Parameters
- **tree** (KDTree/BallTree/BruteTree) - Required - The spatial index structure.
- **point** (Vector/Matrix) - Required - The query point or matrix of points.
- **skip_func** (Function) - Optional - Predicate function to skip specific indices.

### Response
- **idx** (Int/Vector) - Index of the nearest neighbor.
- **dist** (Float/Vector) - Distance to the nearest neighbor.
```

--------------------------------

### All-Points Single Nearest Neighbor Search with allnn

Source: https://context7.com/kristofferc/nearestneighbors.jl/llms.txt

Finds the single nearest neighbor for every point in the tree, automatically excluding the query point itself.

```julia
using NearestNeighbors

data = rand(3, 1000)
kdtree = KDTree(data)

# Find single nearest neighbor for every point
idxs, dists = allnn(kdtree)
# idxs: Vector of 1000 indices (nearest neighbor for each point)
# dists: Vector of 1000 distances
```

--------------------------------

### Inspecting Spatial Regions of BallTree Nodes

Source: https://context7.com/kristofferc/nearestneighbors.jl/llms.txt

Iterates through the leaves of a BallTree and retrieves the spatial region (HyperSphere) for each leaf node. Shows how to access the center and radius of the sphere.

```julia
using NearestNeighbors

data = rand(3, 10_000)
balltree = BallTree(data)
for node in leaves(balltree)
    sphere = treeregion(node)  # HyperSphere
    println("Leaf center=$(sphere.center), radius=$(sphere.r)")
end
```

--------------------------------

### k-Nearest Neighbor Search (knn)

Source: https://context7.com/kristofferc/nearestneighbors.jl/llms.txt

Finds the k-nearest neighbors for a given query point or set of points.

```APIDOC
## knn(tree, point, k, [sortres], [skip_func])

### Description
Finds the k-nearest neighbors for a query point or matrix of points.

### Parameters
- **tree** (KDTree/BallTree/BruteTree) - Required - The spatial index structure.
- **point** (Vector/Matrix) - Required - The query point or matrix of points.
- **k** (Int) - Required - Number of neighbors to find.
- **sortres** (Bool) - Optional - Whether to sort results by distance (default: false).
- **skip_func** (Function) - Optional - Predicate function to skip specific indices.

### Response
- **idxs** (Vector/Vector of Vectors) - Indices of the nearest neighbors.
- **dists** (Vector/Vector of Vectors) - Distances to the nearest neighbors.
```

--------------------------------

### Visualize Node Types

Source: https://github.com/kristofferc/nearestneighbors.jl/blob/master/examples/balltree_illustration.ipynb

Differentiates between leaf nodes and internal nodes using distinct colors.

```julia
col_leaf = RGB(1.0, 0.5, 1.0)  # Brighter magenta for better visibility on dark background
col_internal = RGB(0.3, 0.6, 0.8)

fig = CairoMakie.Figure(backgroundcolor=:gray15)
ax = Axis(fig[1, 1], aspect = DataAspect(), title = "Nodes (leaf nodes in magenta)",
          backgroundcolor=:gray20)

for node in PreOrderDFS(treeroot(tree))
    col = isempty(children(node)) ? col_leaf : col_internal
    add_sphere(ax, treeregion(node), col)
end

fig
```

--------------------------------

### Inspecting Spatial Regions of KDTree Nodes

Source: https://context7.com/kristofferc/nearestneighbors.jl/llms.txt

Iterates through a KDTree using `preorder` and retrieves the spatial region (HyperRectangle) for each node. Differentiates between leaf and internal nodes based on children.

```julia
using NearestNeighbors

data = rand(3, 10_000)
kdtree = KDTree(data)

# Inspect spatial regions
for node in preorder(kdtree)
    rect = treeregion(node)  # HyperRectangle for KDTree
    isleaf = isempty(children(node))
    if isleaf
        println("Leaf: X=[$(rect.mins[1]), $(rect.maxes[1])]")
    else
        println("Internal: X=[$(rect.mins[1]), $(rect.maxes[1])]")
    end
end
```

--------------------------------

### Range Search with inrange

Source: https://context7.com/kristofferc/nearestneighbors.jl/llms.txt

Finds all points within a specified radius of a query point. Returns only indices. Supports single point, multiple points, sorting results, and pre-allocated search with `inrange!`.

```julia
using NearestNeighbors

data = rand(3, 10_000)
balltree = BallTree(data)

# Find all points within radius
point = rand(3)
radius = 0.1
idxs = inrange(balltree, point, radius)
# idxs: [317, 983, 4577, 8675, ...]  (all points within radius 0.1)

# Multiple points query
points = rand(3, 20)
idxs = inrange(balltree, points, radius)
# idxs: Vector of 20 vectors, each containing neighbor indices

# Sort results
idxs = inrange(balltree, point, radius, true)  # sortres=true

# Pre-allocated search with inrange! (must start empty)
idxs_buf = Int[]
inrange!(idxs_buf, balltree, point, radius)
```

--------------------------------

### Range Searches

Source: https://github.com/kristofferc/nearestneighbors.jl/blob/master/README.md

Finds all neighbors within a specified radius `r` of given point(s).

```APIDOC
## Range Searches

A range search finds all neighbors within the range `r` of given point(s). This is done with the methods:

```julia
inrange(tree, point[s], radius) -> idxs
inrange!(idxs, tree, point, radius)
```

* `tree`: The tree instance.
* `point[s]`: A vector or matrix of points to find neighbors for.
* `radius`: Search radius.

Note: Distances are not returned, only indices.

### Request Example

```julia
using NearestNeighbors
data = rand(3, 10^4)
r = 0.05
point = rand(3)

balltree = BallTree(data)
idxs = inrange(balltree, point, r)
println(idxs)

# Updates `idxs`
idxs = Int32[]
inrange!(idxs, balltree, point, r)
println(idxs)

# counts points without allocating index arrays
neighborscount = inrangecount(balltree, point, r)
println(neighborscount)
```

### Response Example

```julia
# Example output for inrange:
# 4-element Array{Int64,1}:
#  317
#  983
# 4577
# 8675

# Example output for inrange! (after update):
# [317, 983, 4577, 8675]

# Example output for inrangecount:
# 4
```
```

--------------------------------

### Single Nearest Neighbor Search with nn

Source: https://context7.com/kristofferc/nearestneighbors.jl/llms.txt

Finds the single nearest neighbor to a point. Can be used for a single query point or multiple points. A skip predicate can be provided to exclude certain points.

```julia
using NearestNeighbors

data = rand(3, 10_000)
kdtree = KDTree(data)

# Single point - returns single index and distance
point = rand(3)
idx, dist = nn(kdtree, point)
# idx: 4523 (index of nearest point)
# dist: 0.023 (distance to nearest point)

# Multiple points - returns vectors of indices and distances
points = rand(3, 50)
idxs, dists = nn(kdtree, points)
# idxs: [4523, 1892, 7234, ...]  (50 nearest neighbor indices)
# dists: [0.023, 0.031, 0.019, ...]  (50 distances)

# With skip predicate
skip_func = i -> i == 100  # Skip point 100
idx, dist = nn(kdtree, point, skip_func)
```

--------------------------------

### Iterating Over Leaf Nodes with AbstractTrees

Source: https://context7.com/kristofferc/nearestneighbors.jl/llms.txt

Iterates directly over the leaf nodes of the tree using AbstractTrees.jl. Retrieves points and original data indices for each leaf.

```julia
for leaf in Leaves(root)
    pts = leafpoints(leaf)
    indices = leaf_point_indices(leaf)  # Original data indices
    println("Leaf contains indices: $indices")
end
```

--------------------------------

### Self-Pair Range Search with inrange_pairs

Source: https://context7.com/kristofferc/nearestneighbors.jl/llms.txt

Finds all pairs of points within the tree that are within a given radius of each other. Works with KDTree, BallTree, and BruteTree. Supports sorting pairs and skipping points with a predicate.

```julia
using NearestNeighbors

data = rand(3, 500)
kdtree = KDTree(data)

# Find all pairs within radius 0.1
radius = 0.1
pairs = inrange_pairs(kdtree, radius)
# pairs: [(1, 5), (2, 47), (3, 89), (4, 156), ...]
# Each tuple (i, j) where i < j means points i and j are within distance 0.1

# Sort pairs by indices
pairs = inrange_pairs(kdtree, radius, true)  # sortres=true

# With skip predicate
skip_func = i -> i > 250  # Only consider first 250 points
pairs = inrange_pairs(kdtree, radius, false, skip_func)

# Works with BallTree and BruteTree too
balltree = BallTree(data)
pairs = inrange_pairs(balltree, radius)

brutetree = BruteTree(data)
pairs = inrange_pairs(brutetree, radius)
```

--------------------------------

### Count Neighbors within Range with inrangecount

Source: https://context7.com/kristofferc/nearestneighbors.jl/llms.txt

Counts the number of points within a specified radius of a query point. Supports single point and multiple points queries.

```julia
using NearestNeighbors

data = rand(3, 10_000)
balltree = BallTree(data)

# Count neighbors for a single point
point = rand(3)
radius = 0.1
count = inrangecount(balltree, point, radius)
# count: 47 (number of points within radius)

# Count for multiple points
points = rand(3, 20)
counts = inrangecount(balltree, points, radius)
# counts: [47, 52, 38, 41, ...]  (20 counts)
```