How to avoid overhead while still implementing null object pattern?

Question

I am implementing a binary search tree in java. Inside the BST class I have a protected class Node (in case I want to extend to an AVL tree). The code is below. I had a problem, both conceptually and aesthetically, implementing empty nodes as null pointers. So instead I opted for the null object pattern and created an EmptyNode object, the code for which is also below. However, even though this gives me prettier code and something more conceptually pleasing (to me), I now have the problem that when I'm working with a tree of height n, I can have as many as 2^{n+1} - 2^{n} instances of this EmptyNode class floating around, which takes up space for no good reason.

How should I fix this code to avoid this overhead while still implementing the null object pattern? I feel like the EmptyNode should be something conceptually similar to a constant field of Node, but I can't implement that. I also feel like there should be only one copy of EmptyNode being referenced anywhere, but I can't figure out how to implement that either. Any help or recommendations are appreciated.

protected class Node<Key,E>{
 protected Key key;
 protected E value;
 protected Node<Key,E> left;
 protected Node<Key,E> right;
 protected int height;
 protected int balanceFactor;
 public Node(){}
 public Node(Key k, E v){
 key = k;
 value = v;
 left = new EmptyNode<Key,E>();
 right = new EmptyNode<Key,E>();
 height = 0;
 balanceFactor = 0;
 }
 public Node(Key k, E v, Node<Key,E> l, Node<Key,E> r){
 key = k;
 value = v;
 left = l;
 right = r;
 height = Math.max(l.height(), r.height())+1;
 balanceFactor = l.height() - r.height();
 }
 public Key getKey(){return key;}
 public E getValue(){return value;}
 public Node<Key,E> getLeft(){return left;}
 public Node<Key,E> getRight(){return right;}
 public int height(){return height;}
 public int balanceFactor(){return balanceFactor;}
 public void setKey(Key k){key = k;}
 public void setValue(E v){value = v;}
 public void setLeft(Node<Key,E> l){
 left = l;
 height = Math.max(l.height(), this.right.height())+1;
 balanceFactor = left.height() - this.right.height();
 }
 public void setRight(Node<Key,E> r){
 right = r;
 height = Math.max(this.left.height(), r.height())+1;
 balanceFactor = this.left.height() - right.height();
 }
 public boolean isEmpty(){return false;}
 public boolean isLeaf(){
 return (left.isEmpty()) && (right.isEmpty());
 }
 public boolean hasLeft(){
 return !left.isEmpty();
 }
 public boolean hasRight(){
 return !right.isEmpty();
 }
}
protected final class EmptyNode<Key,E> extends Node<Key,E>{
 public EmptyNode(){
 key = null;
 value = null;
 left = right = null;
 height = -1;
 balanceFactor = 0;
 }
 @Override
 public void setKey(Key k){}
 @Override
 public void setValue(E v){}
 @Override
 public void setLeft(Node<Key,E> l){}
 @Override
 public void setRight(Node<Key,E> r){}
 @Override
 public boolean isEmpty(){return true;}
 @Override
 public boolean isLeaf(){return false;}
 @Override
 public boolean hasLeft(){return false;}
 @Override
 public boolean hasRight(){return false;}
}

• hmp: Why does your empty node even provide getKey() and getValue() methods? It does not make sense to ask for key or value of an empty node, so the type system should disallow that. (Also, you can call setKey(x) on an empty node but later getKey() returns null. This behavior is very confusing, I wouldn't expect an instance of Node to behave like that).
• user127741: @hmp I agree, I haven't used those methods elsewhere on an EmptyNode and I will alter the code to reflect that. However, this code is working and that always counts for something when you can't appease your OCD.
• Doval: What stops you from having a single instance of an empty node in a static variable? Any time you need an empty node, grab that one.
• Brandon: If an EmptyNode cannot safely be used in the same context as any other node (for example, you end up with lots of if (node instanceof EmptyNode), that suggests it is not really a Node. So why force it to be a Node when it is not? It's a matter of opinion, sure, but I learned early in my SE career the downsides to forcing things that are not the same to be the same (essentially using polymorphism for types that are not compatible).
• Brandon: Again, my own opinion, but OperationNotSupportedException is a sign of what I described: forcing a class to appear compatible with something that it is not truly compatible with. This is used several times in the solution below.

Answer 1

Create a single instance of EmptyNode<Object, Object>, and cast it to Node<Key, E> when you need an empty node for a specific key and value type. This will work because an empty node has null key and value, and null reference can be casted to any reference type. See the source code for Collections.emptyList() for an example of this approach.

A fully working code example:

public class NodeTest {
 protected static class Node<Key,E>{
 private static final Node<?, ?> EMPTY_NODE = new EmptyNode<>();
 protected Key key;
 protected E value;
 protected Node<Key,E> left;
 protected Node<Key,E> right;
 protected int height;
 protected int balanceFactor;
 public Node() {
 this(null, null);
 }
 public Node(Key k, E v){
 this(k, v, Node.<Key, E>emptyNode(), Node.<Key, E>emptyNode());
 }
 public Node(Key k, E v, Node<Key,E> l, Node<Key,E> r){
 this(k, v, l, r, Math.max(l.height(), r.height())+1, l.height() - r.height());
 }
 private Node(Key k, E v, Node<Key, E> l, Node<Key, E> r, int h, int bf) {
 key = k;
 value = v;
 left = l;
 right = r;
 height = h;
 balanceFactor = bf;
 }
 public Key getKey(){return key;}
 public E getValue(){return value;}
 public Node<Key,E> getLeft(){return left;}
 public Node<Key,E> getRight(){return right;}
 public int height(){return height;}
 public int balanceFactor(){return balanceFactor;}
 public void setKey(Key k){key = k;}
 public void setValue(E v){value = v;}
 public void setLeft(Node<Key,E> l){
 left = l;
 height = Math.max(l.height(), this.right.height())+1;
 balanceFactor = left.height() - this.right.height();
 }
 public void setRight(Node<Key,E> r){
 right = r;
 height = Math.max(this.left.height(), r.height())+1;
 balanceFactor = this.left.height() - right.height();
 }
 public boolean isEmpty(){return false;}
 public boolean isLeaf(){
 return (left.isEmpty()) && (right.isEmpty());
 }
 public boolean hasLeft(){
 return !left.isEmpty();
 }
 public boolean hasRight(){
 return !right.isEmpty();
 }
 /**
 * @return empty node. This method can be useful for subclasses
 */
 @SuppressWarnings("unchecked")
 protected static final <Key, E> Node<Key, E> emptyNode() {
 return (Node<Key, E>) EMPTY_NODE;
 }
 }
 private static final class EmptyNode<Key, E> extends Node<Key, E> {
 private EmptyNode() {
 super(null, null, null, null, -1, 0);
 }
 @Override
 public void setKey(Key k){throw new UnsupportedOperationException();}
 @Override
 public void setValue(E v){throw new UnsupportedOperationException();}
 @Override
 public void setLeft(Node<Key,E> l){throw new UnsupportedOperationException();}
 @Override
 public void setRight(Node<Key,E> r){throw new UnsupportedOperationException();}
 @Override
 public boolean isEmpty(){return true;}
 @Override
 public boolean isLeaf(){return false;}
 @Override
 public boolean hasLeft(){return false;}
 @Override
 public boolean hasRight(){return false;}
 }
 public static void main(String[] args) {
 Node<String, Integer> node = new Node<>("hello", 5);
 System.out.println(node.isEmpty()); // prints false
 System.out.println(node.isLeaf()); // prints true
 System.out.println(node.getLeft().isEmpty()); // prints true
 System.out.println(node.getRight().isEmpty()); // prints true
 }
}

My previous solution was bad. The new solution is better: shorter, and re-using more of your code. My modifications of your code were the following.

• Routed all constructor calls to the private constructor which initializes all the fields (key, value, left, right, balanceFactor). This way, if you want to expand the fields a Node holds, you have to alter the assignment statements in only one constructor, reducing the potential for error.
• Implemented public no-arguments constructor for a Node (yours did not initialize the left and right subtrees to be empty, they were null). Now it actually creates a changeable node with initial null key and value.
• Extended Node to get EmptyNode. The EmptyNode constructor just calls super to create a node with null key, value, left and right subtrees, height of -1 and balanceFactor of 0.
• Added emptyNode() method, which returns an appropriately casted EmptyNode instance (see the description of this technique at the beginning of my answer). This method can be used by subclasses of Node to obtain the shared EmptyNode instance instead of creating their own.
• Made setKey(), setValue(), setLeft() and setRight() of EmptyNode throw UnsupportedOperationException, signaling that the empty node is immutable.
• Made Node and EmptyNode static classes. I believe most inner classes should be static unless you absolutely have to use their containing class's fields and methods.

• user127741: I've been attempting to apply this approach to my code, but it's an understatement to say that it has been frustrating. I have a couple questions. First, shouldn't EmptyNode<Key, E> extend Node<Key, E> so that it has the same fields? Second, do you mean 'implements INode<Key,E>' in your 4th to last line? Third, should there be some parens after 'EmptyNode<>'? And why don't you specify the generics with it?
• Nikolai Amelichev: If you use Java 7 and later, you can omit the specification of generics if it is apparent from the context, e.g. List<String> myList = new ArrayList<>() and public List<String> getList() { return new ArrayList<>(); }. Google for "diamond operator Java 7" to see more examples of this.
• Nikolai Amelichev: It also might be more logical for empty node to: 1) return empty left and right subnodes, instead of null (see my comment in the updated code); 2) disallow setting the key and value (say, by throwing an UnsupportedOperationException, which is customary for Java Collections framework).
• user127741: I got something to compile with the intended functionality. I had to change some INodes to Nodes though. I'm working out the final details. (These classes and the interface you helped with are actually wrapped in a larger class in the final code and I had to add a static keyword to the class Node; that caused some problems unrelated to what we discussed here). I'll post a link to the final code within a day.
• Nikolai Amelichev: No problem. I added the static keyword to Node and got rid of the INode (the interface here is not strictly needed.) See my updated (again) answer :-)