Implementing a k-d Tree in JavaScript

K-d trees are a space-partitioning data structure used for organizing points in a k-dimensional space. They are particularly useful for nearest neighbor searches and range queries, enabling efficient retrieval of data points within a specified region. This challenge asks you to implement a k-d tree in JavaScript, focusing on core functionalities like insertion, searching, and potentially deletion (optional).

Problem Description

You are tasked with creating a JavaScript class representing a k-d tree. The tree should be able to store points in a k-dimensional space (where k is a parameter you'll define). The class should include the following methods:

• constructor(k): Initializes the k-d tree with a specified dimension k.
• insert(point): Inserts a new point (an array of numbers) into the tree. The point must have exactly k dimensions.
• searchNearestNeighbor(point, maxResults = 1): Finds the maxResults nearest neighbors to a given query point (also an array of numbers with k dimensions). Returns an array of the nearest neighbor points.
• buildTree(points, depth = 0): (Internal method, not directly called by the user) Recursively builds the k-d tree from an array of points. The depth parameter determines the current dimension to split on (cycling through 0 to k-1).

Key Requirements:

• The tree should be balanced as much as possible during insertion. A simple median-based splitting strategy is sufficient.
• The searchNearestNeighbor method should return the maxResults closest points to the query point, sorted by distance (closest first).
• Handle edge cases gracefully, such as empty trees or invalid input points.

Expected Behavior:

• Insertion should maintain the k-d tree structure, splitting along different dimensions at each level.
• Nearest neighbor search should efficiently traverse the tree to find the closest points.
• The tree should be able to handle points with floating-point coordinates.

Edge Cases to Consider:

• Empty tree: What happens when you try to search in an empty tree?
• Duplicate points: How should the tree handle inserting the same point multiple times? (Allowing duplicates is fine, but consider the impact on performance).
• Invalid input: What happens if a point doesn't have the correct number of dimensions?
• Query point outside the range of existing points.
• maxResults is larger than the number of points in the tree.

Examples

Example 1:

Input:
k = 2
points = [[2, 3], [5, 4], [9, 6], [4, 7], [8, 1], [7, 2]]
tree = new KdTree(k);
for (const point of points) {
  tree.insert(point);
}
queryPoint = [6, 3];
nearestNeighbors = tree.searchNearestNeighbor(queryPoint, 2);

Output:
[[7, 2], [5, 4]]
Explanation:
The points [7, 2] and [5, 4] are the two nearest neighbors to [6, 3] based on Euclidean distance.

Example 2:

Input:
k = 3
points = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
tree = new KdTree(k);
for (const point of points) {
  tree.insert(point);
}
queryPoint = [0, 0, 0];
nearestNeighbors = tree.searchNearestNeighbor(queryPoint, 1);

Output:
[[1, 2, 3]]
Explanation:
[1, 2, 3] is the nearest neighbor to [0, 0, 0].

Example 3: (Edge Case)

Input:
k = 2
points = []
tree = new KdTree(k);
queryPoint = [1, 1];
nearestNeighbors = tree.searchNearestNeighbor(queryPoint, 3);

Output:
[]
Explanation:
The tree is empty, so there are no nearest neighbors to return.

Constraints

• k (the number of dimensions) will be between 1 and 10 (inclusive).
• Each point will be an array of numbers.
• The number of points to insert will be between 0 and 1000 (inclusive).
• The coordinates of each point will be numbers (integers or floats).
• The searchNearestNeighbor method should return results within a reasonable time (e.g., less than 1 second for 1000 points).

Notes

• Consider using a recursive approach for building the tree and searching for nearest neighbors.
• Euclidean distance is the standard distance metric for k-d trees.
• The splitting dimension should cycle through 0 to k-1 at each level of the tree.
• You can optimize the search by pruning branches of the tree that are unlikely to contain closer points. This is a key optimization for k-d tree performance.
• Focus on correctness and clarity first. Performance optimizations can be added later.
• You don't need to implement deletion in this challenge.