121. Introducing the K-D Tree data structure

A K-D Tree (also referred to as a K-dimensional tree) is a data structure that is a flavor of Binary Search Tree (BST) dedicated to holding and organizing points/coordinates in a K-dimensional space (2-D, 3-D, and so on). Each node of a K-D Tree holds a point representing a multi-dimensional space. The following snippet shapes a node of a 2-D Tree:

private final class Node {
  private final double[] coords;
  private Node left;
  private Node right;
  public Node(double[] coords) {
    this.coords = coords;
  }
  ...
}

Instead of a double[] array, you may prefer java.awt.geom.Point2D, which is dedicated to representing a location in (x, y) coordinate space.

Commonly, K-D Trees are useful for performing different kinds of searches such as nearest-neighbor searches and range queries. For instance, let’s assume a 2-D space and a bunch of (x, y) coordinates in this space:

double[][] coords = {
  {3, 5}, {1, 4}, {5, 4...