title: Having a static nested class be a subtype of the enclosing class when trying to implement a Tree data type
body: <p>I have been following along in the book Data Structures (Into Java) by Paul Hilfinger and I am having trouble implementing some part of a Tree structure.</p>
  
  <p>When during the implementation, the book suggested that we have a nested static class represent an empty tree to make so methods using a Tree do not have to check for null pointers. The example code looks like this </p>
  
  <pre><code>public class Tree&lt;T&gt; {
  
      public Tree(T label) ...
      public Tree(T label, int k) ...
      public T label() ...
      public int degree() ...
      public int numChildren() ...
      public Tree&lt;T&gt; child(int k) ...
      public void setChild(int k, Tree&lt;T&gt; C) ...
      public boolean isEmpty() { return false }
  
      public final Tree&lt;T&gt; EMPTY = new EmptyTree();
  
      static class EmptyTree&lt;T&gt; extends Tree&lt;T&gt; {
  
          private EmptyTree() {}
          public boolean isEmpty() { return true }
          public int degree() { return 0 }
          public int numChildren() { return 0 }
          public Tree&lt;T&gt; getChild(int i) {
              throw new Exception;
          }
          public T label() {
              throw new Exception;
          }
      }
  }
  </code></pre>
  
  <p>Here is my implementation:</p>
  
  <pre><code>public class NonEmptyGTree&lt;T&gt; {
  
      public NonEmptyGTree(T label, int arity) {
          this.label = label;
          children = (NonEmptyGTree&lt;T&gt;[]) new Object[arity];
          for (int i = 0; i &lt; arity; i++) 
              children[i] = EMPTY;
      }
  
      public NonEmptyGTree() {
  
      }
  
      public NonEmptyGTree&lt;T&gt; getChild(int i) {
          return children[i];
      }
  
      public void setChild(int i, NonEmptyGTree&lt;T&gt; set) {
          if (children[i].isEmpty()) deg += 1;
          children[i] = set;
      }
  
      public T getLabel() {
          return label;
      }
  
      public void setLabel(T label) {
          this.label = label;
      }
  
      public int numChildren() {
          return children.length;
      }
  
      public int degree() {
          return deg;
      }
  
      public boolean isLeaf() {
          return deg == 0;
      }
  
      public boolean isEmpty() {
          return false;
      }
  
      public class EmptyGTree&lt;T&gt; extends NonEmptyGTree&lt;T&gt; {
  
          private EmptyGTree() {}
  
          public int degree() { return 0; }
  
          public int numChildren() {
              return 0;
          }
  
          public NonEmptyGTree&lt;T&gt; getChild(int i) {
              throw new IllegalStateException();
          }
  
          public void setChild(int i, NonEmptyGTree&lt;T&gt; set) {
              throw new IllegalStateException();
          }
  
          public T getLabel() {
              throw new IllegalStateException();
          }
  
          public void setLabel(T label) {
              throw new IllegalStateException();
          }
  
          public boolean isEmpty() {
              return true;
          }
      }
  
      private T label;
      private NonEmptyGTree[] children;
      private int deg = 0;
      public final NonEmptyGTree&lt;T&gt; EMPTY = new EmptyGTree&lt;T&gt;();
  }
  </code></pre>
  
  <p>This made sense to me since that way we won't have to check for null pointers when we use trees elsewhere, but when I try to initialize a tree, it goes into a loop with the Tree initializing EMPTY then EMPTY calling super() which then initializes Tree again looping.</p>
  
  <p>I then tried to use a Null design pattern where I made a Tree interface and and then had two files implementing it, one for an empty tree and a nonempty tree. This seems messy to me because then for any subtype of a Tree, I would have to split it up into a nonempty tree and empty tree for every subtype. It seems like the idea of making an empty tree should stop with just this one implementation since functionally all empty trees are the same (if you do not need to access the parent nodes).</p>
  
  <p>Is it not possible to make it so that I would only have to implement the EmptyTree once? Or is what I am asking to do not possible?</p>