How scikit-learn implements KDTree KNN

Our eight training rows each have two numeric features and a class label. We'll call a row of coordinates a point. Rows 0–3 sit near the origin with label A; rows 4–7 sit near (10, 10) with label B. The query is (0.2, 0.1), and we want its three nearest training rows and a label predicted from them.

The calls do different jobs. Creating KNeighborsClassifier(...) only stores these settings; it can't build a tree because it hasn't seen any training rows. model.fit(X, y) supplies coordinates and labels, checks the input, stores the class information and builds the tree from the coordinates. A final group that the builder stops dividing is a leaf.

After fitting, model.kneighbors(Q) returns, for each query, the distances and original row IDs of its neighbors. model.predict(Q) runs the same neighbor search and then votes with the stored labels, so you don't need to call kneighbors first; we do it here to inspect the result. A direct KDTree(X, ...) receives coordinates in its constructor, so that call builds the tree immediately and has no separate fit. Estimator source

The builder chooses groups from coordinates only. Labels don't choose the splits, and this path doesn't drop coordinates into fixed bins; it compares actual feature values. Labels become relevant only after the neighbor IDs are found, which is why flipping a label in the lab never moves the rings, only the vote.

Input checks also shape the path. It rejects empty training data and nonfinite coordinates, and queries must have the same number of features as the training data. For an explicit query, k can't exceed the number of training rows. Fitting with an oversized n_neighbors can succeed, but the later neighbor request fails (pick n_neighbors = 9 in the lab). The no-argument query excludes each training row itself and has a stricter limit, covered in §9.

import numpy as np
from sklearn.neighbors import KNeighborsClassifier

X = np.array([
    [0,0], [0,1], [1,0], [1,1],
    [10,10], [10,11], [11,10], [11,11],
], dtype=np.float64)
y = np.array(["A", "A", "A", "A", "B", "B", "B", "B"])
Q = np.array([[0.2, 0.1]], dtype=np.float64)
model = KNeighborsClassifier(
    n_neighbors=3, algorithm="kd_tree", leaf_size=1,
    metric="euclidean", weights="uniform", n_jobs=1,
)
model.fit(X, y)
distances, row_ids = model.kneighbors(Q)
assert row_ids.tolist() == [[0, 2, 1]]
assert np.allclose(distances[0], np.sqrt([0.05, 0.65, 0.85]))
assert model.predict(Q).tolist() == ["A"]

X has shape (8, 2) and Q has shape (1, 2). Both returned arrays have shape (1, 3): three neighbors for one query, nearest first.

Describe groups using original row IDs

Before splitting the eight-row example, take four one-feature rows: values [10, 0, 11, 1] with labels [B, A, B, A]. We want one group holding values 0 and 1 and another holding 10 and 11. We could copy values and labels into new arrays, but a real row can have hundreds of features, and copying every coordinate each time we divide a group repeats a lot of work. All we need to record is which existing rows belong together.

Each row already has an original row ID: its zero-based position in the training array. The tree moves those small integers into group order and leaves coordinates and labels where they are. KDTree stores this ID array as idx_array. A slot is a position in this ID array; slot 1 holding ID 3 is a different fact from row 3's value. Tree storage source

Follow an ID to the coordinate and label

To read X[ids[1]], first read ids[1], which is ID 3, then read X[3], which is 1. The label is still at y[3], which is A. One array supplies the index used to read another, which is called indirect indexing, and it keeps each value and label connected through their shared row ID. In the eight-row example X[3] is the pair [1, 1], and one feature of it is X[3, feature].

Record a group with its start and stop slots

The first group's IDs occupy slots 0 and 1, so it is ids[0:2]: the start is included and the stop excluded, so its length is 2 − 0 = 2. Such a range is half-open. The two ranges 0:2 and 2:4 cover 0:4 exactly, with no overlap and no missing slot. Each tree group records its range as idx_start and idx_end, and each group gets a node number that identifies the group's record, not a training row; one node can describe many rows.

Change IDs without losing a row

Changing entries inside an existing array is mutation. Tree construction mutates the ID array and keeps coordinate rows in their original order. Every original ID must remain present exactly once, which makes the arrangement a permutation. Exchanging two IDs preserves that property. Assigning ids[0] = ids[1] alone doesn't: the old ID in slot 0 disappears and the other appears twice. The lab's "Assign" button shows exactly that failure.

Describing a group is different from gathering its values. In NumPy, X[ids] is advanced indexing and creates a new array of copied values. A basic slice such as ids[0:2] is a view that shares storage with the original. The compiled tree reads an ID and then a coordinate whenever it needs one, so it never creates that gathered array. NumPy copies and views

import numpy as np

X = np.array([10, 0, 11, 1])
y = np.array(["B", "A", "B", "A"])
ids = np.array([1, 3, 0, 2])

row_id = ids[1]
assert row_id == 3
assert X[row_id] == 1
assert y[row_id] == "A"
assert ids[1:3].tolist() == [3, 0]
assert X[ids[1:3]].tolist() == [1, 10]

# This display array owns copied values, not references to X's values.
gathered = X[ids]
assert gathered.tolist() == [0, 1, 10, 11]
assert not np.shares_memory(X, gathered)
gathered[0] = -100
assert X.tolist() == [10, 0, 11, 1]

# A basic NumPy slice shares its selected storage with the original array.
id_slice = ids[0:2]
assert np.shares_memory(ids, id_slice)

In the eight-row example the initial group covers ID slots 0:8, and its children will cover 0:4 and 4:8. Next we need to put the right rows' IDs into each range.

Use eight one-feature rows so every comparison is visible: row IDs 0–7 hold values 8 1 6 3 7 2 5 4. The left child should get the four rows with smaller values and the right child the other four. Order inside either child doesn't matter for this split, so 1 3 2 4 | 5 7 8 6 describes the same two groups as the fully sorted 1 2 3 4 | 5 6 7 8. A full sort would also decide the order inside each child, and we can leave that work undone.

To make the groups, we need the fifth-smallest value: four smaller values go before it, and it plus the three larger ones go right. Here we can see the answer is 5, but the procedure has to find it with comparisons, without assuming the values are 1 through 8.

Compare the rows with one trial value

Compare every value with 4. Reading left to right, the smaller ones collect into [1, 3, 2] and the larger ones into [8, 6, 7, 5]. The trial value is the pivot, and separating values by comparison with it is partitioning. The lists still aren't sorted, but we've learned something about order: three values are smaller than 4, so they take the first three sorted places and 4 takes the fourth. We want the fifth, so the answer is the smallest value of [8, 6, 7, 5]. We can stop comparing the smaller group for this search; it stays in the training data, we've just finished using it to find the split.

Count positions again inside the remaining group

Zero-based, the fifth place is index 4. Inside the new list of larger values, we removed four earlier places (three smaller values and the pivot), so the index we seek becomes 4 − 3 − 1 = 0. That 0 means "first in this list's sorted order", not the first value currently written, which is 8. Partition [8, 6, 7, 5] around 6 and you get smaller [5], pivot [6], larger [8, 7]. Index 0 comes before the pivot's index 1, so the answer lies in [5], and a one-value list answers itself. When we continue in the smaller group, nothing was removed before it, so the index stays the same; the subtraction applies only when we continue in the larger group.

Finding a value by its place in sorted order is selection, and the requested zero-based position is its rank. Repeatedly partitioning and continuing in the one group that can contain the rank is the idea behind Quickselect. CMU selection notes, Cornell Quickselect

Choose which group to examine next

Say the requested index within the current group is r and a values are smaller than the pivot, so the pivot would sit at index a:

This rule renumbers each new list from zero. §4 keeps one full ID array instead, whose slot numbers never change, so its requested slot stays fixed too.

For eight rows, scikit-learn uses 8 // 2 = 4 as the slot where the right child starts (// is integer division). That's not the statistical median, which averages the fourth and fifth values to get 4.5. The split needs an actual row at the first position of the right child, so it selects the fifth value, 5. Construction source

The temporary lists made the comparisons easy to follow, but the same work can happen inside the existing ID array: read feature values from X, and exchange the IDs of rows that belong in different places. X never changes. Our teaching procedure uses the row in the last active slot as the pivot (ID 7, value 4) and leaves it there while it inspects the other seven IDs.

The code tracks two slot numbers. scan is the slot whose ID we inspect next, and write is where the next ID that precedes the pivot should go. Slot 0 holds ID 0 with value 8, which is larger than 4, so it stays and only scan moves. Slot 1 holds ID 1 with value 1, which belongs before the pivot, so IDs 1 and 0 trade places. We already compared value 8 when its ID sat in slot 0, and moving the ID doesn't change X[0], so the displaced row doesn't need another look. The exchange needs a saved copy of one ID (saved = ids[0]) because assigning into slot 0 first would lose the only record of which row lived there.

Keep the requested slot fixed while the range gets smaller

After the first partition the pivot finishes at slot 3, so the fifth-smallest row must be in slots 4–7. We're still working in the same full ID array, where slot 4 remains slot 4, so the target stays 4 and the next comparisons are restricted to ids[4:8]. Its pivot is 8; everything else is smaller and already sits where a smaller row's ID should go, so each exchange is with itself and the pivot stays at slot 7. The range shrinks to 4:7 with pivot 5, which lands at slot 4, the target. The left child gets IDs [1, 3, 5, 7] and the right child [6, 2, 4, 0]. The right child happens to come out sorted for this input, but the procedure never needed that.

Why the exchanges keep working

During a partition, slots before write hold rows already found to precede the pivot (green in the lab), and slots from write up to scan hold rows checked and found not to precede it (grey). If the next row precedes, exchanging it with the ID at write puts it in the green region, and the displaced ID was already checked, so it can join the grey region without creating unfinished work. If it doesn't precede, advancing scan simply extends the grey region. A description that stays true after every step like this is an invariant, and it's why the pivot can be dropped into slot write at the end.

After a partition, we exclude the pivot and one side from further selection work, and later exchanges stay inside the remaining range, so they can't disturb the order already established across its edges. The range shrinks every round, so it must eventually place a pivot at the target or shrink to the one row there. The builder still needs both children; searching one side to find the dividing row doesn't remove the other side from the tree.

Give equal feature values a definite comparison order

The running example has repeated first coordinates, [0, 0, 1, 1, 10, 10, 11, 11]. The inspected source compares original row IDs when feature values match, so row 0 comes before row 1. Every row has a distinct ID, so this rule can order any two rows, and "comes before the pivot" means a smaller value, or an equal value with a smaller ID. It doesn't preserve incoming order: IDs arriving as [5, 2] come out with 2 first. Preserving incoming order would be stable sorting, and selection promises neither stability nor sorted children. Comparison source Pick the "all equal" preset in the lab to watch ID tie-breaking do all the work.

import numpy as np

def row_precedes(X, a, b, feature):
    """Compare original rows a and b by one feature, then by row ID."""
    a_value = X[a, feature]
    b_value = X[b, feature]
    if a_value == b_value:
        return a < b
    return a_value < b_value

def select_ids(X, ids, start, stop, feature):
    """Mutate ids so the parent's middle rank occupies its target slot."""
    if not (0 <= start < stop <= len(ids)):
        raise ValueError("Selection needs a nonempty valid ID range.")

    target = start + (stop - start) // 2
    lo = start
    hi = stop
    while hi - lo > 1:
        pivot_slot = hi - 1
        pivot_id = ids[pivot_slot]
        write = lo

        # range(lo, pivot_slot) excludes the reserved pivot slot.
        for scan in range(lo, pivot_slot):
            if row_precedes(X, ids[scan], pivot_id, feature):
                saved = ids[write]
                ids[write] = ids[scan]
                ids[scan] = saved
                write += 1

        # Put the pivot after all rows that precede it.
        saved = ids[write]
        ids[write] = ids[pivot_slot]
        ids[pivot_slot] = saved

        if write == target:
            return target
        if target < write:
            hi = write
        else:
            lo = write + 1

    # One active row remains. Its slot must be the requested target.
    return target

X = np.array([[8], [1], [6], [3], [7], [2], [5], [4]])
original_X = X.copy()
ids = [0, 1, 2, 3, 4, 5, 6, 7]
middle = select_ids(X, ids, 0, 8, 0)
assert middle == 4
assert ids == [1, 3, 5, 7, 6, 2, 4, 0]
assert X[ids, 0].tolist() == [1, 3, 2, 4, 5, 6, 7, 8]
assert np.array_equal(X, original_X)
assert sorted(ids) == list(range(8))   # Every original row remains once.

# Check the required cross-boundary property, including the selected row.
for left_slot in range(0, middle):
    for right_slot in range(middle, 8):
        assert row_precedes(X, ids[left_slot], ids[right_slot], 0)

# Duplicate feature values are ordered for comparison by original row ID.
X_equal = np.array([[4], [4], [4], [4]])
equal_ids = [3, 1, 2, 0]
middle = select_ids(X_equal, equal_ids, 0, 4, 0)
assert middle == 2
assert equal_ids[middle] == 2
assert sorted(equal_ids[:middle]) == [0, 1]

# The smallest valid selection contains one row and needs no partition.
one_id = [0]
assert select_ids(np.array([[7]]), one_id, 0, 1, 0) == 0
assert one_id == [0]

The final ID array in these assertions belongs to this teaching function and input. scikit-learn calls std::nth_element, whose contract doesn't prescribe these pivots or exchanges, so a correct library result can order IDs differently inside either child. It must still put the requested row at the boundary and satisfy every comparison across it. §13 covers the real call.

Back to the eight two-feature rows. We can divide rows by one feature; to build the tree we also need to choose that feature, keep dividing the resulting groups, and record where each group lies.

Choose the feature with the largest range

We want groups a query can tell apart by location, and a feature that extends over a wide range is one direction for separating them. For each feature, subtract its smallest value from its largest; that difference is its spread. At the root both features span 0 to 11, a tie, and the source replaces its chosen feature only on a strictly larger spread, so feature 0 wins. Inside each child both spreads are 1, so feature 0 wins again, giving leaves [0, 1], [2, 3], [4, 5] and [6, 7].

Largest spread is a heuristic: a sensible choice from available information with no guarantee of the fastest later queries. The source doesn't alternate features by level and doesn't compute variances. Split-feature source Our rows already arrive in an order matching these groups, so the installed 1.8.0 tree leaves the ID array as [0, 1, …, 7]. That observed order isn't a promise about nth_element on other inputs.

Put a box around each group's actual points

Leaf rows (0, 0) and (0, 1) always have first coordinate 0 and second coordinate between 0 and 1, so the intervals feature 0: [0, 0] and feature 1: [0, 1] describe every member. These intervals form the group's bounding box; this one has zero width in feature 0, which is fine because both points lie on one vertical line. The source scans member rows for each feature's minimum and maximum, giving the smallest axis-parallel box containing the group. A tight box matters: a wider region extending into empty space could look close to a query even when both members are far away. The source scans coordinates for every node's box, and at a node it splits, the split-feature routine scans for minima and maxima again rather than reusing the box. Box source

Finish the first child before returning to the second

Number the root 0, its children 1 and 2, then 3, 4 under node 1 and 5, 6 under node 2. The builder starts node 0 and calls its build procedure for node 1; node 0 waits for that call to finish. Node 1 calls node 3 and waits in turn. When node 3 has its box and leaf record, that call ends and node 1 resumes. Calling the same function on a smaller problem is recursion; each call keeps its own node and its place in the procedure. The visit order is 0, 1, 3, 4, 2, 5, 6. Selection followed only one side to find a dividing row, but construction must build both sides, because both contain rows a later query might need.

Store node records and boxes in arrays

The source uses each node number as an array position: the children of node i are at 2i + 1 and 2i + 2. The position tells the query where each child is, so no separate child pointers are needed. Positions follow level order even though construction visits nodes depth-first.

The radius measures from the box's center to a corner. For the square from (0, 0) to (1, 1) the center is (0.5, 0.5) and the radius is √(0.5² + 0.5²) ≈ 0.7071, so a sphere of that radius contains the box. The main query prunes with box distances; the dual-tree search in §14 also uses the radius when it decides which group to divide. The records don't store the split feature or threshold: once child ranges and boxes exist, the query uses them directly and never repeats construction decisions. Node-storage source

import numpy as np
from sklearn.neighbors import KDTree

X = np.array([[0,0],[0,1],[1,0],[1,1],
              [10,10],[10,11],[11,10],[11,11]], dtype=np.float64)
tree = KDTree(X, leaf_size=1, metric="euclidean")
data, ids, records, boxes = tree.get_arrays()
assert data.shape == (8,2)
assert records.shape == (7,)
assert boxes.shape == (2,7,2)
assert ids.tolist() == list(range(8))  # Observed for this installed example.
assert records["idx_start"].tolist() == [0,0,4,0,2,4,6]
assert records["idx_end"].tolist() == [8,4,8,2,4,6,8]
assert records["is_leaf"].tolist() == [0,0,0,1,1,1,1]
for node in range(7):
    start = records[node]["idx_start"]
    stop = records[node]["idx_end"]
    members = X[ids[start:stop]]
    assert np.array_equal(boxes[0,node], members.min(axis=0))
    assert np.array_equal(boxes[1,node], members.max(axis=0))

The tree is built. The query reads this stored arrangement and never rebuilds the groups.

Calculate a point distance one coordinate at a time

The query is q = (0.2, 0.1) and row 0 is (0, 0). The differences are 0.2 and 0.1, their squares 0.04 and 0.01, and the sum 0.05; √0.05 is the ordinary Euclidean distance. The four nearby rows have squared distances 0.05, 0.85, 0.65 and 1.45 (rows 0–3). Square roots preserve the order of nonnegative numbers, so the search can compare squared distances throughout and take roots only for the final output. For D features:

The source calls the comparison value a reduced distance. For Euclidean distance it's the squared distance; other metrics use other conversions, so "reduced" doesn't always mean "squared".

Find the nearest possible position in a box

The far group's first coordinate lies in [10, 11], and even its nearest allowed value, 10, is 9.8 from the query's 0.2. Its second coordinate also lies in [10, 11], at least 9.9 from 0.1. So every point in that box has squared distance at least 9.8² + 9.9² = 96.04 + 98.01 = 194.05. That number is a lower bound: no member's distance can be smaller, so we can reason about the whole group before reading a single point.

Each member coordinate lies inside its interval, so its gap can't be smaller than the table's gap, and squaring and adding nonnegative gaps preserves the inequality. That proves the box value bounds every member's squared distance. The nearest allowed position need not be a training point: the leaf holding (1, 0) and (1, 1) allows (1, 0.1), at squared distance 0.64, while its nearest actual point is at 0.65. Written compactly, with endpoints lj, uj:

When the query is outside, one endpoint expression is the positive gap; inside, both are nonpositive and the maximum is zero. KDTree bound source, Princeton rectangle distance

Follow the coordinate loops

The tree runs these loops in compiled Cython: they read numeric coordinates and add contributions without creating a NumPy difference array per point. Once the search has kept k rows, the largest of their distances is its cutoff, and a new row must be closer than that to improve the result. The inspected Euclidean point loop doesn't receive the cutoff, so it can't stop partway through a point when the partial sum gets too large; skipping a group avoids whole point calculations, but it doesn't shorten this loop. Point-distance source

import numpy as np

q = np.array([0.2, 0.1])
x = np.array([1.0, 0.0])
point_squared = 0.0
for feature in range(2):
    difference = q[feature] - x[feature]
    point_squared += difference * difference
assert np.isclose(point_squared, 0.65)

low = np.array([10.0, 10.0])
high = np.array([11.0, 11.0])
bound_squared = 0.0
for feature in range(2):
    if q[feature] < low[feature]:
        gap = low[feature] - q[feature]
    elif q[feature] > high[feature]:
        gap = q[feature] - high[feature]
    else:
        gap = 0.0
    bound_squared += gap * gap
assert np.isclose(bound_squared, 194.05)

When we visit a point, we store its distance with its original row ID. If we've kept [0.05, 0.85, 0.65] and a new distance 0.2 arrives, it should replace 0.85, the largest. Scanning the list for its maximum on every arrival becomes real work for large k, and the box tests need that same maximum. We want it in a known place without sorting after every change.

Put the largest retained distance at slot zero

Arrange the distances as [0.85, 0.05, 0.65]: slot 0 holds the largest, and its children, slots 1 and 2, hold the others in either order. For bigger arrays, require every parent to be at least as large as each child, with the children of slot i at 2i + 1 and 2i + 2, just like the node layout. Following parents toward slot 0 never reaches a smaller value, so slot 0 holds a maximum. This is a max heap; the entries here are neighbor distances, not tree groups, and the shared numbering serves two separate structures. MIT heap notes

A retained row is a candidate, one of the best neighbors among the points checked so far, and the root is the cutoff. Distances and IDs live in two arrays whose matching slots form one pair, so every move must move the ID too.

Start with three unused places

Before any point is visited, all three distances are infinity. Infinity compares larger than every finite distance, so a real point can replace an unused entry through the same comparison used for later improvements. The source starts the ID entries at zero, but they're placeholders: three zeros don't mean row 0 was accepted three times (the lab shows them as "unused"). Candidate-array source The cutoff stays infinite until three real points are retained; with only two, the third neighbor is unknown and any distant group might contain it.

Fill the heap, then replace the worst row

Row 0 arrives at 0.05. It beats the infinite root, but parking it at the root would break the heap rule because its children are still infinite. So the update keeps the incoming pair in hand, moves the larger child up (both are infinity; this code picks the left child on a tie), and places the pair in slot 1, giving [∞, 0.05, ∞]. Row 1 at 0.85 promotes the right infinity and lands in slot 2. Row 2 at 0.65 meets the last unused root, promotes 0.85, and lands in its old slot: [0.85, 0.05, 0.65] with IDs [1, 0, 2]. Row 3 at 1.45 is rejected because 1.45 ≥ 0.85.

To see a replacement in a full heap, start from [1.2, 0.4, 0.1] with IDs [42, 1, 5] and push (0.2, row 4). It beats 1.2, so row 42 leaves. Of the root's children, move the larger, (0.4, row 1), to the root, then put the new pair in that child's old slot, giving [0.4, 0.2, 0.1] and IDs [1, 4, 5]. Promoting the larger child matters: moving 0.1 up would leave 0.4 under a smaller parent. In a bigger heap the comparison repeats down the chosen branch until the pair fits or reaches a childless slot, which is called sifting down.

The source writes the incoming pair at the root first and keeps it in local variables while children are copied upward over it, so the arrays don't form a valid heap during each individual assignment (step through a push in the lab to see the duplicate). The completed update restores the rule and every pair. Fixed-size heap source The test value >= values[0] rejects a value equal to the cutoff, and a one-entry heap needs no moves: an accepted value simply replaces slot 0.

import numpy as np

def push_candidate(values, ids, value, row_id):
    if value >= values[0]:
        return False
    values[0] = value
    ids[0] = row_id
    current = 0
    size = len(values)
    while True:
        left = 2 * current + 1
        right = left + 1
        if left >= size:
            break
        larger = left
        if right < size and values[right] > values[left]:
            larger = right
        if value >= values[larger]:
            break
        values[current] = values[larger]
        ids[current] = ids[larger]
        current = larger
    values[current] = value
    ids[current] = row_id
    return True

values = [float("inf"), float("inf"), float("inf")]
ids = [0,0,0]
assert push_candidate(values, ids, 0.05, 0)
assert values == [float("inf"), 0.05, float("inf")]
assert push_candidate(values, ids, 0.85, 1)
assert values == [float("inf"), 0.05, 0.85]
assert push_candidate(values, ids, 0.65, 2)
assert np.allclose(values, [0.85,0.05,0.65])
assert ids == [1,0,2]
assert not push_candidate(values, ids, 1.45, 3)

values, ids = [1.2,0.4,0.1], [42,1,5]
assert push_candidate(values, ids, 0.2, 4)
assert values == [0.4,0.2,0.1]
assert ids == [1,4,5]
assert not push_candidate(values, ids, 0.4, 99)  # Equal to cutoff: reject.

single_value, single_id = [float("inf")], [0]
assert push_candidate(single_value, single_id, 0.2, 4)
assert single_value == [0.2] and single_id == [4]

We now have every piece: the tree gives each group's row range and box, a box gives a lower bound on its point distances, and the heap gives the worst retained distance. At each node, compare the squared box bound with the current cutoff. If the bound is larger, no point in the node can improve the result, so the query returns immediately; skipping a group this way is pruning. If the node survives and is a leaf, calculate all member distances and offer each pair to the heap. If it's internal, calculate both child bounds, visit one child, then the other. Even a leaf gets the pruning test before any point work. Depth-first query source

Visit the more promising child first

At the root, node 1's box contains the query (bound 0) and node 2's bound is 194.05. Visiting node 1 first gives the search a chance to find close points quickly, and close points lower the cutoff, which can let it skip node 2 when its turn comes. So the source visits the child with the smaller bound first, and the first child on a tie. Either order finds correct neighbors, but the order changes how much work it takes. A smaller bound doesn't guarantee a closer actual point, since the nearest position in a box might hold no row, but the bound is already computed for pruning, so using it for ordering is free.

What the five node entries show

The default trace enters nodes 0, 1, 3, 4, 2. Node 3 accepts rows 0 and 1, node 4 accepts row 2 and rejects row 3, and by the time node 0 resumes and calls node 2, the cutoff has fallen from infinity to 0.85, so 194.05 > 0.85 prunes the far group. Rows 4–7 get no point calculations at all. The root computed both child bounds before visiting node 1, and keeping them is safe because the query and boxes don't change. The cutoff does change, so node 2's entry must read the heap's current root; reusing the infinite cutoff from the time the bounds were computed would still give correct neighbors but miss this prune.

Finishing one child's work before returning to the other is depth-first search. The waiting function calls form the call stack, the saved information about where each call resumes, and the recursion provides that storage for free. MIT depth-first search

Why skipped points can't change the result

After each completed heap update, the real candidates are the best neighbors among the points checked so far (with ties, the heap may keep any one of the tied rows), and unused entries keep the cutoff infinite until k real candidates exist. Once the heap is full, every retained distance is at most the root, so if a box's lower bound exceeds the root, every point in that box is farther than every retained candidate. An internal node that passes the test visits both children, and a leaf that passes scans its rows, so every training point is accounted for: either the query checks it, or it skips a group whose valid bound excludes it. That's why pruning preserves a correct result in general, beyond the numbers in this example.

Two comparisons use slightly different rules. The query prunes only when bound > cutoff, while the heap rejects a point when value >= cutoff, so a box exactly at the cutoff is still visited. With eight identical points and k = 1, the first point makes the cutoff 0, every box bound is also 0, and 0 > 0 is false, so the query calculates all eight distances (pick "Eight identical points" in the lab). It still returns a correct zero-distance neighbor.

import numpy as np
from sklearn.neighbors import KDTree

X = np.array([[0,0],[0,1],[1,0],[1,1],
              [10,10],[10,11],[11,10],[11,11]], dtype=np.float64)
Q = np.array([[0.2,0.1]])
tree = KDTree(X, leaf_size=1, metric="euclidean")
tree.reset_n_calls()
distances, ids = tree.query(Q, k=3)
assert ids.tolist() == [[0,2,1]]
assert np.allclose(distances[0] ** 2, [0.05,0.65,0.85])
assert tree.get_n_calls() == 4
assert tree.get_tree_stats() == (1,2,2)

same = KDTree(np.zeros((8,2)), leaf_size=1, metric="euclidean")
same.reset_n_calls()
distances, ids = same.query(np.zeros((1,2)), k=1)
assert distances[0,0] == 0
assert same.get_n_calls() == 8

reset_n_calls() resets the point-distance counter, which doesn't count box checks. get_tree_stats() reports pruned nodes, visited leaves and expanded internal nodes, the same tuple the lab shows.

Put the pairs in nearest-to-farthest order

The query ended with squared distances [0.85, 0.05, 0.65] and IDs [1, 0, 2], an order that kept the cutoff easy to read but isn't what the caller wants. The default result lists the nearest first: sort the complete pairs by squared distance to get [0.05, 0.65, 0.85] with IDs [0, 2, 1], then take roots, [0.223607, 0.806226, 0.921954]. Sorting only the distance array would attach the nearest distance to row 1, which is wrong; the IDs move with their distances. Waiting until the end saves work: the search only ever needed the maximum, and squared distances gave every comparison without repeated roots.

The pinned source obtains the heap arrays, optionally sorts them, converts reduced distances to ordinary ones, and only then chooses which arrays to return, so return_distance=False doesn't skip the sorting and square-root work in this source. Direct-tree sort_results=False controls sorting separately. Query-output source

Look up the labels and count votes

During fitting, the classifier turns labels into integer codes: with classes_ = ["A", "B"], code 0 means A and code 1 means B. A returned row ID retrieves that row's stored code, and after counting, the winning code converts back through classes_. Our IDs [0, 2, 1] all carry A, so uniform voting gives A three votes, and predict_proba divides each class total by the sum to give [1, 0]. Classification source

Now keep the coordinates and change the labels to [A, B, B, A, B, B, B, B]. The same IDs retrieve [A, B, B], so uniform voting predicts B, two votes to one. With weights="distance", each neighbor contributes the reciprocal of its ordinary distance: A gets 1/0.223607 ≈ 4.472136 and B gets about 1.240347 + 1.084652 = 2.324999, so the prediction flips to A, with probabilities about [0.657944, 0.342056]. Using 1/0.05 instead of 1/√0.05 would be a different rule from scikit-learn's.

Handle an exact match and two different kinds of tie

A zero distance has no finite reciprocal. If any returned neighbor of a query has distance zero, the implementation gives those neighbors weight 1 and every other returned neighbor weight 0, so only exact matches decide that query's weighted vote. Weight source With one-feature coordinates [0, 0, 1], labels [B, A, B], query 0 and k = 3, the two exact matches give one vote each to B and A and the third row gives nothing. The totals tie, and a tied vote selects the first class in classes_, which is A.

A tie in class totals is different from a tie at the final neighbor distance. If two rows are equally far and only one place remains, which one enters the heap depends on visit order: the heap rejects a distance equal to its root, and the final sorter adds no row-ID tie rule. Construction's feature-then-ID comparisons don't promise that queries keep the smallest IDs among equal-distance neighbors, and if tied rows have different labels, keeping a different row can change the vote.

import numpy as np
from sklearn.neighbors import KNeighborsClassifier

X = np.array([[0,0],[0,1],[1,0],[1,1],
              [10,10],[10,11],[11,10],[11,11]], dtype=np.float64)
y = np.array(["A","B","B","A","B","B","B","B"])
Q = np.array([[0.2,0.1]])
uniform = KNeighborsClassifier(n_neighbors=3, algorithm="kd_tree",
    leaf_size=1, metric="euclidean", weights="uniform").fit(X,y)
weighted = KNeighborsClassifier(n_neighbors=3, algorithm="kd_tree",
    leaf_size=1, metric="euclidean", weights="distance").fit(X,y)
assert uniform.predict(Q).tolist() == ["B"]
assert weighted.predict(Q).tolist() == ["A"]
assert np.allclose(weighted.predict_proba(Q)[0], [0.6579442,0.3420558])

zero = KNeighborsClassifier(n_neighbors=3, algorithm="kd_tree",
    weights="distance").fit(np.array([[0.],[0.],[1.]]), ["B","A","B"])
assert zero.classes_.tolist() == ["A","B"]
assert zero.predict([[0.]]).tolist() == ["A"]
assert np.allclose(zero.predict_proba([[0.]])[0], [0.5,0.5])

Decide whether a row can be its own neighbor

model.kneighbors(X) supplies explicit coordinates as queries, so a training row at those coordinates is eligible, including the row itself at distance zero. model.kneighbors() with no array asks for neighbors of each fitted row while excluding that row's own identity; a different row at identical coordinates stays eligible. The no-argument path requests one extra result, removes the querying row's ID, and keeps the requested count. With duplicate points, the row's own ID can be missing from those extra results, and then the implementation removes the last extra neighbor instead. Removing every zero-distance row would be wrong because it would remove valid distinct rows. Self-query source For N training rows, explicit queries need k ≤ N while the self-excluding request needs k < N.

The prediction is complete: rows [0, 2, 1] went through the groups, distance calculations, heap, returned arrays and vote. The rest of the lesson explains the implementation choices behind that trace.

Our leaf_size=1 tree scanned four points. A tree with fewer nodes can scan the same four points while checking fewer boxes:

With setting 2 the four nearby rows form one leaf: the query scans them and prunes the far group. Setting 1 checks two extra boxes inside the nearby group but still calculates all four nearby distances, so more nodes didn't save point work here. Setting 4 has no child boxes to prune with, so its single leaf scans all eight rows. The pinned defaults are leaf_size=30 for KNeighborsClassifier and leaf_size=40 for direct KDTree; we set 1 only to make the splits visible.

Count levels before using the formula

The seven-node tree has one root, two children and four leaves: 1 + 2 + 4 = 7 positions. The source allocates the node array before building, sized for a complete set of levels, and stops splitting when no child position is left. Let H count levels including the root (here 3), so the split depth is h = H − 1 = 2. Each extra level doubles the leaf positions, so there are 2h leaves and 1 + 2 + … + 2H−1 = 2H − 1 nodes; check it with 2³ − 1 = 7. Selection splits each row count as evenly as possible, so leaf counts differ by at most one.

Read the allocation formula

log₂(t) asks which power of two gives t: log₂(8) = 3, and log₂(7) lies between 2 and 3. With N training rows and positive leaf_size L, the source computes:

For N = 8, L = 1: (N − 1)/L = 7, log₂ 7 ≈ 2.807, plus one is 3.807, and int drops the fraction to give H = 3: seven nodes, four leaves, two rows each. For L = 2 the ratio is 3.5 and H = 2; for L = 4 it's 1.75 and H = 1, a single root holding all eight rows. The max(1, …) handles tiny datasets: for N = 1 the ratio is 0 and log₂ 0 is undefined. Subtracting one from N sets the boundary: allowed leaf sizes run from L to 2L, and at exactly N = 2L one leaf is allowed, so using N would add a level there. For N = 8, L = 4 the subtraction keeps all eight rows in one leaf. Allocation source

The builder's ordinary stopping test checks whether child position 2i + 1 would fall outside the allocated array. It doesn't keep splitting until every leaf has at most L rows, which is why leaf_size isn't a strict maximum per leaf.

import numpy as np
from sklearn.neighbors import KDTree

X = np.array([[0,0],[0,1],[1,0],[1,1],
              [10,10],[10,11],[11,10],[11,11]], dtype=np.float64)
Q = np.array([[0.2,0.1]])
observed = []
for leaf_size in [1,2,4,30]:
    tree = KDTree(X, leaf_size=leaf_size, metric="euclidean")
    tree.reset_n_calls()
    distances, ids = tree.query(Q,k=3)
    assert np.allclose(distances[0] ** 2, [0.05,0.65,0.85])
    observed.append((len(tree.get_arrays()[2]), tree.get_n_calls()))
assert observed == [(7,4),(3,4),(1,8),(1,8)]

Find one coordinate in memory

The query sometimes needs X[6, 1], feature 1 of row 6. Our float64 matrix is stored row by row, so reaching row 6 skips two values for each of the six earlier rows (12 values), and feature 1 skips one more: 13 elements in, and at eight bytes each, a byte offset of 13 × 8 = 104. A NumPy array keeps its numbers in a buffer, a block of memory, plus information about rows, columns, element type and layout. The dtype says how each number is represented: float64 uses eight bytes, float32 four. When each row immediately follows the previous one, the layout is C-contiguous, and the byte steps to advance one row (16) or one feature (8) are its strides, so the same offset is 6 × 16 + 1 × 8 = 104. A Fortran-contiguous matrix stores columns consecutively instead, and a view taking every other row leaves gaps; their strides describe those different steps. NumPy memory layout

Give compiled code the type and layout it needs

Cython describes an existing buffer with a typed memoryview that fixes the numeric type, the number of dimensions and the permitted layout. The compiler can then turn a coordinate read into address arithmetic like the calculation above, so the loop over features reads stored numbers directly instead of creating a Python number and running Python operations for every coordinate. NumPy supplies the storage; compilation decides how the inner loop uses it. Cython memoryviews The keyword const prevents writes through that particular view, but it doesn't make other references read-only: if the caller can still write to the original array, those writes show up through the compiled view.

Check when the coordinates are copied

The public KDTree path requests C-contiguous float64 coordinates. The source also generates 32-bit and 64-bit variants, but this public path uses the float64 one. If the input already has that type and layout, the tree can share its buffer; otherwise conversion creates another buffer. A Fortran-ordered matrix, a float32 array, and a float64 view selecting every other row all get copied. The estimator can also keep a validated float32 _fit_X while its tree stores converted float64 coordinates, so one logical dataset can occupy two buffers, and checking only the estimator's dtype would miss the tree's copy. Input conversion source

Keep shared coordinates consistent with the boxes

Suppose the tree shares X's buffer, and after fitting you change row 4 from (10, 10) to the query (0.2, 0.1). The tree's next coordinate read sees the new point, but the far group's stored box still runs from (10, 10) to (11, 11). The query uses that old box to skip the group before ever reading row 4, and misses a point whose true distance is now zero. Rebuild the tree after changing training coordinates, or keep the indexed buffer from being changed through another reference: sharing saves a copy only while the stored groups and boxes still describe the values.

import numpy as np
from sklearn.neighbors import KDTree, KNeighborsClassifier

X = np.array([[0,0],[0,1],[1,0],[1,1],
              [10,10],[10,11],[11,10],[11,11]], dtype=np.float64)
tree = KDTree(X, leaf_size=1, metric="euclidean")
assert np.shares_memory(tree.get_arrays()[0], X)
assert X.strides == (16,8)
assert (6 * X.strides[0] + X.strides[1]) == 104

for changed in [np.asfortranarray(X), X.astype(np.float32),
                np.repeat(X,2,axis=0)[::2]]:
    converted = KDTree(changed, leaf_size=1)
    assert not np.shares_memory(converted.get_arrays()[0], changed)

small = X.astype(np.float32)
model = KNeighborsClassifier(n_neighbors=1, algorithm="kd_tree").fit(small,range(8))
assert model._fit_X.dtype == np.float32
assert model._tree.get_arrays()[0].dtype == np.float64

Q = np.array([[0.2,0.1]])
X[4] = Q[0]  # Deliberately invalidate the old tree's stored boxes.
distances, ids = tree.query(Q,k=1)
assert ids[0,0] == 0
actual_squared = np.sum((X-Q[0]) ** 2, axis=1)
assert np.argmin(actual_squared) == 4
assert actual_squared[4] == 0
rebuilt = KDTree(X,leaf_size=1,metric="euclidean")
assert rebuilt.query(Q,k=1)[1][0,0] == 4

Let separate queries read the same tree

Different query points can all read the same coordinates, ID array and node boxes, because those describe the fitted dataset. Each query needs its own candidate distances, candidate IDs, and record of which groups remain. The estimator's tree path divides query rows into batches and requests workers, preferring threads; each batch calls the same fitted tree with its own candidate arrays, and the estimator combines results in the original query order. Query batching source The compiled query work releases Python's global interpreter lock (GIL), which otherwise restricts simultaneous execution of Python code, so threads can do native query work concurrently. More threads still don't guarantee faster execution. In this path n_jobs distributes query rows; it doesn't split one query's two child calls across workers, parallelize construction, or select dual-tree search.

Count the operations in our completed query

The query entered five nodes (0, 1, 3, 4, 2) and calculated five box bounds, including the root's. It expanded two internal nodes, scanned two leaves, calculated four point distances, accepted three heap updates and pruned one group. Every point and box calculation handled two coordinates, and even rejected row 3 paid for a complete distance; its 1.45 only avoided heap repair.

The box loops do work proportional to V·D and the point loops P·D. Heap repair follows at most one downward branch: seven positions allow at most two child moves, fifteen allow three, and roughly doubling capacity adds one possible move, which is why logarithms describe that part. Big-O notation describes how a bound on work grows with input size while dropping fixed multipliers and smaller terms; O(D) means doubling D roughly doubles the counted operations. It isn't a measurement of seconds. For one query, including default output preparation:

The first term counts box and point loops, the second accepted heap repairs, and the third bounds sorting the final k results; initializing k infinite entries, square roots and output writes are linear in k and fit inside it. Writing k + 1 keeps the expression meaningful for k = 1, where a one-slot heap still needs comparisons and assignments. Rejected updates need a comparison too, which fits inside the point term for D ≥ 1. Class voting can add more: in the inspected weighted_mode, each distinct selected class causes another scan of the batch's Q·k codes and weights, so an unconditional O(k) voting cost would be wrong for that implementation. Weighted-mode source

Count repeated selection work

Selection can inspect many rows in its first partition and still do work proportional to the input overall; what matters is how many rows it must inspect again. If eight rows shrink to four, then two, then one, counting one unit per active row gives 8 + 4 + 2 + 1 = 15, and sixteen rows give 31: doubling the input keeps the total just under twice the input. In general n + n/2 + n/4 + … < 2n, and with fixed comparison and exchange work per row, that pattern is linear, O(n). That's an illustration of useful shrinkage, not a claim that every partition halves the rows. Randomized Quickselect has expected linear work, averaged over its random pivots, and the C++ nth_element contract specifies average linear complexity without prescribing any pivot policy. C++ contract

Now give the last-pivot teaching function increasing values [1, …, 8] and ask for the smallest. The pivot is always the largest remaining value, so each round removes only the pivot: comparisons 7 + 6 + … + 1 = 28, which is n(n − 1)/2 and grows as n², called quadratic. The answer stays correct; the bad pivots make it expensive. Asking for the middle row doesn't remove the problem: target slot 4 gives scans of 8, 7, 6, 5 rows and 7 + 6 + 5 + 4 = 22 comparisons, and for even n about n/2 rounds each compare about n/2 rows. Sorting by partitions must continue into both groups, so each level of a balanced run still handles about n rows, over about log₂ n levels: O(n log n) for balanced Quicksort, which can also turn quadratic with bad pivots. Selection follows one group, which is where its saving comes from.

Count construction by tree level

At the root, computing the box reads N·D coordinates. At the next level the two children together still hold all N rows, so their boxes read another N·D, and the same holds at every complete level. With h + 1 levels, box construction costs O(N·D·(h + 1)); split-feature scans add another coordinate scan at internal levels, and selection adds average work proportional to the rows per internal level. Together that's O(N·D·(h + 1) + N·h) under the average-selection model, and with a fixed small leaf setting h grows like log₂ N, giving the familiar O(N·D·log N). It isn't a worst-case promise for every C++ library. Construction is paid once at fitting, so many queries spread its cost; with one query, building can cost more than it saves.

Measure when boxes stop saving point calculations

A short root-to-leaf path doesn't guarantee a short search: the query can visit many paths when boxes fail to exclude points, and high dimension and a large k both weaken pruning. The lesson's experiment used 2,048 random training rows, 64 queries and leaf_size=16 in the installed build, counting point distances rather than timing:

Both 20-feature cases calculate every training distance for every query, while the two-feature cases skip most of them, less so at k = 128. These results don't establish a universal dimension cutoff or a ranking by elapsed time. The lab below reruns the same experiment design on its own random data in your browser, sweeping D.

import numpy as np
from sklearn.neighbors import KDTree

observed = []
for D, k in [(2,3),(2,128),(20,3),(20,128)]:
    rng = np.random.default_rng(42)
    X = rng.random((2048,D))
    queries = rng.random((64,D))
    tree = KDTree(X,leaf_size=16,metric="euclidean")
    tree.reset_n_calls()
    distances, ids = tree.query(queries,k=k)
    observed.append(tree.get_n_calls())
    for query_id in range(64):
        all_squared = np.sum((X-queries[query_id]) ** 2,axis=1)
        expected = np.sort(all_squared)[:k]
        assert np.allclose(distances[query_id] ** 2, expected)
        assert np.allclose(all_squared[ids[query_id]], expected)
assert observed == [3424,20128,131072,131072]

Count distinct memory buffers

In this 64-bit runtime, each float64 coordinate and each pointer-sized row ID takes eight bytes, and a node record takes 32: three pointer-sized integers and a float64 radius (the leaf flag is stored as an integer, not a one-byte Boolean). For our tree that's 128 bytes of coordinates, 64 of IDs, 224 of node records and 224 of box corners, 640 in all. If the tree shares the caller's coordinate buffer, those 128 bytes exist once; if conversion made a copy, count both. These figures exclude Python object headers, labels, metric objects, waiting calls and temporary outputs. In general the main buffers use O(ND + N + MD), with M growing like N/L. Candidate distances and IDs add 16·Q·k bytes, depth-first waiting calls use space proportional to h, and §14's searches need more.

Translate the selection arguments

The teaching function in §4 used explicit Python indices. The scikit-learn wrapper asks the C++ standard library to do the selection (a source excerpt, not a standalone program):

std::nth_element(
    node_indices,
    node_indices + split_index,
    node_indices + n_points,
    index_comparator);

The arguments identify the start, the requested position and the end of an ID range, followed by the comparison rule. These location values are pointers: a pointer identifies where data is stored, and adding 4 advances by four ID elements without changing any ID or coordinate. node_indices + n_points points just past the last ID, a boundary marker the algorithm never reads. If the parent occupies global slots 4:8, its starting pointer already refers to slot 4, so a relative split_index = 2 identifies global slot 6, the same relative-versus-global distinction as in rank adjustment. index_comparator reads feature values through the IDs and falls back to IDs on ties. The call rearranges the existing IDs, so no ids = … assignment is needed. Partition wrapper

Separate the contract from the pivot strategy

nth_element must put the requested element where it would sit in a fully sorted range and arrange both sides so their comparisons respect that boundary. It doesn't promise sorted children, the incoming order of ties, or any pivot sequence, and the nonparallel overload used here has an average linear complexity requirement. C++ standard contract Each C++ library chooses how to meet it. Our always-last-pivot function shows the partition mechanism, but its work depends on input order and it has no fallback when pivots keep removing one row, so its trace says nothing about a library's pivot policy or worst case.

GCC 14's libstdc++, for example, samples the second, middle and last positions and pivots on the middle-valued sample: for values 9, 2, 7 it picks 7, which is neither the value at the middle sampled position (2) nor necessarily the median of the whole range. For a range of n rows it allows 2·floor(log₂ n) partition rounds; if that runs out, with the requested row at zero-based rank r in the remaining range, the fallback keeps the r + 1 smallest rows in a max heap, whose largest member is then the requested row. That gives an O(n log n) worst case. GCC 14 selection source The Microsoft STL main source examined on 2026-10-10 samples three or nine values, monitors how much the range shrinks, and falls back to grouping values in fives for a worst-case linear bound. Microsoft STL source These are examples of policies, not a claim about what's inside the installed wheel. The standard gives an average linear requirement, and stronger worst-case guarantees depend on the library and version.

Sort the returned pairs in the pinned fork

The final output sort is separate from construction's selection: it takes the retained distance/ID pairs and orders every position. For our three squared distances [0.85, 0.05, 0.65] the fork uses insertion sort: start with the first entry as the ordered part, move 0.05 before 0.85, then move 0.65 left past 0.85, giving [0.05, 0.65, 0.85], with each ID moving alongside. The source uses insertion sort for ranges of at most 15 entries. Larger ranges are partitioned around pivots with both sides sorted, and too many successive partitions trigger a switch to heapsort; that combination is introsort. The initial partition-depth limit is 2·floor(log₂ k), so k = 32 allows ten levels. Fork sorting source

Build the heap before removing its maximum

When the fallback begins, its range can be in any order left by earlier partitions, so slot 0 isn't necessarily the maximum, and heapsort must first build the max-heap order. With distances [2, 5, 3] and IDs [8, 4, 7], root 2 is smaller than child 5, so exchange those pairs to get [5, 2, 3]. Then exchange the root with the last pair, which puts 5 in its final place, exclude that slot, and repair. The remaining [3, 2] already is a heap, and one more exchange finishes: [2, 3, 5] with IDs [8, 7, 4]. Real introsort would use insertion sort at this size; the tiny trace just makes the mechanism visible.

For a longer range of length m, slots from m // 2 onward have no children. Start at the last parent, m // 2 − 1, and work backward toward slot 0, sifting each parent's pair down toward its larger child as in §7. Working backward is what makes this correct: a child's slot number is larger than its parent's, so by the time a parent is repaired, its subtrees are already heaps (or single leaves), and only the parent's pair can be out of place. After each maximum moves to the finished end, the new root may be too small, so it's repaired within the shortened range before the next removal. The fork explicitly builds the initial heap before removing any maximum. Heap construction and sorting source

The fallback keeps repeated poor partitions from making the final sort quadratic. That's a source claim about the pinned fork; the installed 1.8.0 sorter differs, so the executable examples don't verify which branch of the newer sorter would run.

Let auto choose the search implementation

Our example forced algorithm="kd_tree". With algorithm="auto", the estimator picks a backend, the implementation that performs neighbor search, by applying rules to the inputs and settings; it doesn't time the candidates. For dense Euclidean input in the inspected source, D > 15 or k >= N // 2 sends auto to brute force; otherwise Euclidean is supported by KDTree, so the tree is chosen. For N = 8, D = 2, k = 3 neither holds, so auto picks KDTree, but changing only k to 4 makes 4 >= 8 // 2 true and auto switches to brute force. Other branches handle precomputed distances, sparse input and metric support: some metrics KDTree can't handle go to BallTree, and weighted Minkowski is steered away from KDTree. Auto-selection source

Calculate every distance with organized numeric work

Brute force considers every candidate point, but it can still use compiled operations and batches instead of a slow Python loop. Expanding each square with (a − b)² = a² + b² − 2ab and summing over features gives

so for q = (0.2, 0.1) and x = (1, 0): 0.05 + 1 − 2 × 0.2 = 0.65. A batch can reuse each row's sum of squares and compute many product sums together with matrix multiplication. Blocking means doing this for a manageable subset of query/training pairs at a time: regular numeric work with no point-skipping decisions. Expanding the squares can subtract similar large terms, which changes floating-point rounding, so mathematical equality doesn't promise bit-identical results (try the "large coordinates" preset). Euclidean reduction source, matrix-product source

Choose the next waiting box from all pending boxes

Direct KDTree.query(..., breadth_first=True) keeps a separate collection of pending nodes ordered by box bound and always takes the smallest next. After expanding our root it holds node 1 (bound 0) and node 2 (194.05); taking node 1 adds nodes 3 (0.04) and 4 (0.64), and the choices continue 3, 4, 2, the same order as depth-first here. In another tree, a waiting node from an earlier branch can have a smaller bound than a newly found child, and then the next choice jumps back to that earlier branch. A collection that returns the item with the most urgent key is a priority queue; here the source uses a min heap, whose root holds the smallest pending bound. Breadth-first query source That heap answers "which group runs next?" while the candidate max heap answers "which retained neighbor is farthest?": different objects, opposite orders. Keeping the extra heap costs work and memory, so a better visit order has to save enough to pay for it.

Compare a group of queries with a group of training rows

Direct KDTree.query(..., dualtree=True) builds another tree over the queries and compares one query box with one training box. In one feature, query interval [0, 1] and training interval [10, 11] are at least 10 − 1 = 9 apart, overlapping intervals have gap zero, and squaring and adding the gaps bounds every point pair between the two boxes. To skip a training box for a whole query group, the bound must beat every query's cutoff: with cutoffs 0.5 and 3 and a pair bound of 2, the first query is ruled out but the second could still improve, so the group-wide skip isn't allowed. Compare against the largest cutoff instead; a bound of 4 beats both. Any query with an unused candidate entry has an infinite cutoff, which blocks every finite group-wide skip.

When the pair can't be skipped, smaller boxes might allow useful exclusions. If one side is a leaf, only the other can be divided; if both can, the source uses their stored radii to split the more spatially extended side, a heuristic for making the next bounds more useful, and in the depth-first branch equal radii choose the training side. The implementation stores and updates bounds for query nodes as candidates improve, and when both nodes are leaves it computes their point pairs and updates each query's own candidate heap. Nearby queries share decisions about whole groups, at the cost of a query tree and extra bound storage. Dual-tree source

Keep the eight coordinates, change the query to (10.2, 10.1), keep k = 3, and use labels [A, A, A, A, A, B, B, A]. Work each answer out before checking it; the checker compares your answers with the same engine the labs use.

Choose the next useful step

Each situation states a goal without naming the method. Decide what you'd do and why it helps, then open the card.

Keep the phases distinct when reading source code

The three opening ideas now have concrete examples. Grouping cost includes selecting IDs, scanning coordinates and storing boxes. Partial ordering is enough for a split or a heap update, while the returned neighbors need full ordering. Predicting a class then adds label lookup and voting.

When you assess performance, count boxes and points instead of assuming a balanced tree makes every query logarithmic. When you read compiled loops, follow the coordinate reads instead of attributing all the work to a NumPy expression. When you read a selection call, separate the required child membership from an internal order the function never promised.

All twelve Python examples in the source note were compiled and their asserted blocks executed against the installed build. The fork's C++ and Cython were inspected as source; the fork wasn't compiled into a new package.

Implementation links refer to the pinned fork; supporting tutorials explain general ideas and may use different construction policies or indexing conventions.