Do I need Generics for these node and tree classes?

Instead of using x and y, it would be better to go OO and define a class named Point with inner x and y. When there are many variables they should clearly be grouped in a class. However, it's not clear for only two variables. But for your specific case, you should absolutely group them in one class because you will then be able to re-use your tree class for any classes (make your tree generic).

You should define your tree class as: KDTree<T> (the type T does not extend anything). You can than use your tree as a KDTree<Point> or KDTree<WhateverClass>. As specified by rolfl, Node should be some inner class of KDTree<T> and should not be visible from outside. So, to summarize:

public class KDTree<T> {
   private Node<T> leftChild;
   private Node<T> rightChild;
   ...

   private static class Node<S> {
      private S value;
      private Node next;
      ...
   }
}

rolfl's comment about "equality" of floating point values is also important to consider. You could maybe define a method point1.nearlyEquals(point2) in class Point. Or maybe simply override the equals method.

Choosing between those two options is not trivial (nearlyEquals vs overriding equals). I discuss both choices below, but the discussion is somewhat advanced and convoluted.

If you create a method nearlyEquals, then your class KDTree would call that specific method when calling contains. That means you could not make KDTree generics (KDTree<T>) since it could only be used with nodes of type Point.

If instead you override the equals method in Point, you could keep KDTree<T> generic since contains would just call Object.equals for all types. The downside is that Point becomes a bit weird if equals is fuzzy. You might be aware that you should always override equals and hashCode as a consistent pair. However, I don't think you can redefine the hashCode in a consistent manner with a fuzzy equals. If those are not consistent, you could never use the class Point in a HashMap, for example.

There are many options to solve this dilemma. The simplest is to actually not make a generic KDTree<T>, but just define a KDTree where the child nodes are always of type Points. And since you don't have a generic KDTree anymore, there is no pressing need to group x and y in a Point class.

So we are back to your original solution!

A different solution would be to stick to strict equality for x and y (use the default equals in class Point). But as rolfl mentioned, you can have two points which should be the same, but end up being very slightly different because of rounding error. It is for you to consider how important that might be in your application.

Sorry for my convoluted answer, but I hope nonetheless that you will have learned something from this.

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 && 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 15^th decimal place, or something.

Usually you would use generics in a classes like KDTree if you need to parametrize them at some point. What I mean here is, that you would construct a KDTree containing objects of type Node but also another KDTree but containing objects of type... lets say DifferentNode.

What generics give you is that you have compile time type checks.

You can read more about generics on official documentation: http://docs.oracle.com/javase/tutorial/java/generics/types.html

To summarize: you don't need to use generics in your KDTree class example at all, because you want it to only contain Node objects.

Hope that helps

I agree with the others answers but wanted to explain a bit about how you could do it with generics and what that would mean, so that you can decide on whether or not you want it.

Rolfl says:

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.

Now this is where generics can come in.

Imagine that your Node class would be like this:

There's no need to initialize your leftChild and rightChild to null because they get that as default.

private static class Node<T> {
    private final T data;
    private Node<T> leftChild;
    private Node<T> rightChild;

    private Node(T data) {
        this.data = data;
    }
}

public class KDTree<N> {
    Node<N> root;
    KDTree(Node<N> root) {
        this.root = root;
    }
    ...
}

(Now I see that toto2 has provided more or less the exact same answer)

The important part of generics is that they provide flexibility in what type of data your class uses. If you want to make a KDTree of Points, you can use KDTree<Point>, but in another project you might want to use a KDTree of Cards, so you have KDTree<Card>. Then someday you might want to have a list of KDTrees of Points, so you get List<KDTree<Point>>.

As far as I read the declaration public static class KDTree means "class KDTree contains objects that extends type Node".

I would not read it as "contains", I would simply read it as "of" as I have indirectly implied above. KDTree of Points. KDTree of Cards. They don't necessarily have to contain those types (Points/Cards), but they are probably interacting with them in one way or another - if they're not then the generics can be safely removed.

Is there any way to declare that class KDTree contains only objects of type Node?

If so, you don't need generics at all (as Karolina answered). However, in my example here it is the Node that has the important generics. It can be a node of Points or a node of Cards etc. And as a KDTree of Card-nodes should not work with a Point-nodes, the KDTree also have generics. However, a KDTree probably always uses some kind of nodes so there's no need to use the Node itself as a generic type, unless you want to be able to change the Node implementation itself.