title: Balanced Binary Tree in Java without setters
body: <p>I'm working on a school assignment about creating a balanced binary tree. Interfaces for the Node and the Tree were supplied with declared methods. However, the Node interface had only <code>getLeft</code>, <code>getRight</code> and <code>getValue</code> methods, no setters. Since we submit for grading only the implementation files, I worked around it by using the implementation class itself for typing, instead of the Interface.</p>
  
  <p>When I messaged the teacher, he told me it was possible to implement it using merely the Node constructor, adding a "hint" that "For every node, its child are also trees." which is obvious, but I'm not sure how that is to help me.</p>
  
  <p>It seems to me that without using setters, I'd first need to basically map out the tree in advance and then start building it from bottom instead of from top, which seems needlessly complicated and counter-intuitive. Is there some trick I'm missing?</p>
  
  <p>Thank you for any help or advice you can offer.</p>
  
  <p>My current implementations are as follows:</p>
  
  <p><strong>TreeImpl.java</strong></p>
  
  <pre><code>public class TreeImpl implements Tree {
      private NodeImpl root;
  
      public TreeImpl() {}
  
      @Override
      public void setTree(int[] values) {
          this.root = null;
          Arrays.sort(values);
          recurseSet(values);
      }
  
      private void recurseSet(int[] values) {
          if (values.length &gt; 0) {
              int middleIndex = values.length / 2;
              NodeImpl tempNode = new NodeImpl(values[middleIndex]);
              insert(tempNode, root, 1);
              recurseSet(cutArray(values, 0, middleIndex - 1));
              recurseSet(cutArray(values, middleIndex+1, values.length-1));
          }
      }
  
      private int[] cutArray(int[] array, int begin, int end) {
          int length = end-begin+1;
          int[] newArray = new int[length];
          System.arraycopy(array, begin, newArray, 0, length);
          return newArray;
      }
  
  
      private void insert(NodeImpl node, NodeImpl location, int depth) {
          if (root == null) {
              root = node;
              return;
          }
          if (node.getValue() &lt; location.getValue()) {
              /* left branch */
              if(location.getLeft() == null) {
                  node.setDepth(depth);
                  location.setLeft(node);
              } else {
                  insert(node, location.getLeft(), depth+1);
              }
  
          } else {
              /* right branch */
              if(location.getRight() == null) {
                  node.setDepth(depth);
                  location.setRight(node);
              } else {
                  insert(node, location.getRight(), depth+1);
              }
          }
  
      }
  
      @Override
      public Node getRoot() {
          return root;
      }
  
      private String toString(NodeImpl root) {
          String finalString = "";
          if (root != null) {
              finalString += root;
              finalString += toString(root.getLeft());
              finalString += toString(root.getRight());
          }
          return finalString;
      }
  
      @Override
      public String toString() {
          return toString(root);
      }
  }
  </code></pre>
  
  <p><strong>NodeImpl.java</strong></p>
  
  <pre><code>public class NodeImpl implements Node {
      private int value;
      private NodeImpl left;
      private NodeImpl right;
      private int depth = 0;
  
      public NodeImpl(int value) {
          this.value = value;
      }
  
      public void setLeft(NodeImpl left) {
          this.left = left;
      }
  
      public void setRight(NodeImpl right) {
          this.right = right;
      }
  
      public void setDepth(int depth) {
          this.depth = depth;
      }
  
      @Override
      public NodeImpl getLeft() {
              return left;
      }
  
      @Override
      public NodeImpl getRight() {
          return right;
      }
  
      @Override
      public int getValue() {
          try {
              return value;
          } catch (NullPointerException e) {
              System.out.println("Null pointer.");
          }
          return 0;
      }
  
      @Override
      public String toString() {
          String finalString = "";
          for(int i = 0; i &lt; depth; i++) {
              finalString += " ";
          }
          finalString += "- ";
          finalString += value;
          finalString += "\n";
          return finalString;
      }
  
  }
  </code></pre>