Do I need Generics for these node and tree classes?
I think that you have confused yourself with your code, and the way that data structures are intended to be implemented.

What you have done that is unconventional, and causing the confusion, is that you have exposed the Node class as a public class, and you have a constructor that takes Nodes as input.

Node is normally an implementation detail of a data astructure (your KDTree) that is transparent to others. Consider Java's LinkedList, that has Node instances, but you never see those Node instances, just like ArrayList has an internal array, etc.

Your KDTree should contain the Node class as an inner (nested) private class, and the users of your KDTree should never be able to see/access those nodes. Your KDTree class should abstact that interaction away.

The constructor for your KDTree should be able to construct off the base values of the node, or be an empty constructor, and have an add method that takes the base values.

Consider something that looks like:

public static class KDTree {

    private static class Node{
        int id;
        public double x;
        public double y;
        public Node leftChild;
        public  Node rightChild;

        Node(int id, double x, double y){
            this.id = id;
            this.x = x;
            this.y = y;
            leftChild = null;
            rightChild = null;
        }
    }

    private Node root = null;

    public KDTree(){
        // empty constructor
    }

    public boolean add(int id, double x, double y) {
        Node toadd = new Node(id, x, y);

        .... add toadd to hierarchy....

    }

    public boolean contains(int x, int y) {
        .....
    }

}


Note, the Node is private, and not visible outside the KDTree class.

It is possible that you need some other form of data structure to represent the actual data in the Node, like a Point class, and, your Node could have a reference to a Point instance. Point strikes me as being a data structure you need anyway, and probably already have.

Note that your x and y values are doubles, and any time I see == comparisons with doubles, I caution people that it is not as reliable as you would expect:


if (t.x == root.x &amp;&amp; t.y == root.y)



Be careful there, it's possible that t.x and root.x are very, very, very close to each other, but not quite the same, due to some rounding value in a calculation, or something at the 15th decimal place, or something.