Java Array of Generic Nodes in a Binary Tree, can't create nil node

Question

I'm having a similar problem as in this question: Array of generic nodes Java

However, making the nested Node class static solves the one problem but creates another for me. I've written a Binary Tree, and each time a Node's pointer isn't supposed to point to anything (e.g. a leaf node's left and right pointers, or the root's parent pointer), it actually points to a special "nil" node, which contains no relevant data. Nil is a member variable of the Binary Tree.

When I create a node, the constructor makes all pointers point to nil. However, if I make the Node class static so I can create an array of nodes (which I need to do for a particular method), I get an error for each pointer that says "Cannot make a static reference to the non-static field nil." But if I change nil to be static, I get an error for it which says "Cannot make a static reference to the non-static type T." (My nodes hold parameterized type objects.)

Here's my Node class:

protected static class Node<T>{
    Node left, right, parent;
    T object;

    protected Node(T x) {
        object= x;
        left= nil;
        right= nil;
        parent= nil;
    }
}

This is the nil designation and the Binary Tree constructor, which creates the nil node and makes it the root:

protected static Node<T> nil;

public BT() {
    nil= new Node<T>(null);
    root= nil;
}

How do I allow myself to create an array of nodes without running into these static vs non-static issues?

Is there any reason you aren't simply using null when a pointer isn't supposed to point to anything? Also, the left, right and parent fields should probably be of type Node<T> rather than the raw type Node. — Ted Hopp
Why is the nil field static? Yes, the class may need to be static, but that does not mean that the field nil does too. — Hovercraft Full Of Eels
I'm following a textbook in an online course (Open Data Structures by Pat Morin). Sometimes this guy has some really convoluted code, so it wouldn't surprise me if the nil node is unnecessary. — wames
@HovercraftFullOfEels Because nil is referenced from a static context (in the static nested Node constructor). — Andreas
@HovercraftFullOfEels I agree, but if you want to write code without using null values, then that's how. See e.g. Are null references really a bad thing? I personally disagree. Replacing null with nil doesn't really make the code less error-prone when only used inside the implementation of class. Eliminating null from the API, by e.g. using Optional, is a different story. — Andreas

Andreas Andreas · Accepted Answer · 2019-07-03T23:37:30

First, never use raw generics, so specify <T> on the Node fields:

protected static class Node<T> {
    Node<T> left, right, parent;
    T object;

Next, to initialize nil, you need a difference constructor:

protected Node() {
    left = this;
    right = this;
    parent = this;
}

Now you can initialize nil as a non-static object, to keep type-safety:

protected Node<T> nil = new Node<>();

Though, rather than creating a nil object for every tree, create a static method:

@SuppressWarnings("rawtypes")
private static Node NIL = new Node();

@SuppressWarnings({ "cast", "unchecked" })
protected static <T> Node<T> nil() {
    return (Node<T>) NIL;
}

Java Array of Generic Nodes in a Binary Tree, can't create nil node

1 Answers