Implement K-Nearest Neighbors

A company's asset performance management classifier needs to assign an integer condition class to a new sensor-feature vector using exact k-nearest neighbors. Implement an efficient KNN predictor without using machine-learning libraries.

Formal Specification

Implement knn_predict(points, labels, query, k).

• points is a list of n feature vectors, where every vector contains d integers.
• labels[i] is the integer class for points[i].
• query is a feature vector with d integers.
• Return the predicted integer label from the k nearest points using squared Euclidean distance.

Build a balanced KD-tree, then search it with backtracking. If multiple points have equal distance, prefer the smaller original point index. Class prediction uses: highest vote count, then smallest total squared distance among tied classes, then smallest label.