title: Java insert method in complete binary tree almost working
body: <p>I asked this before, but I still haven't been able to fix the insert() method inside my CompleteTree class. I'm trying to create a complete binary tree (not a binary search tree - it doesn't matter what the value inside the tree node is). So the following:</p>
  
  <pre><code>public static void main(String[] args) {
      CompleteTree tree = new CompleteTree();
      tree.insert(1);
      tree.insert(2);
      tree.insert(3);
      tree.insert(4);
      tree.insert(5);
      tree.insert(6);
      tree.inorder();
  }
  </code></pre>
  
  <p>should create a tree that looks like this: </p>
  
  <pre><code>                1
                /   \
              2       3
             / \     /
           4    5   6
  </code></pre>
  
  <p>And it should print out 4 2 5 1 6 3</p>
  
  <p>At first I thought my code worked, but I quickly realized there was a problem. My insertions will work up to 11. However, when I try inserting 12, it becomes a left child of 8 instead of 6. </p>
  
  <pre><code>                  1
                /      \
               2         3
             /   \      /  \ 
           4      5    6    7
          / \    / \     
         8   9  10 11  
  // Code works fine up to this point
  </code></pre>
  
  <p>After reviewing my code, I can see why 12 gets inserted there, and I can see the problem with my code, but I have no idea how I would go about fixing it so that the nodes get inserted in the correct order. Any help would be greatly appreciated!</p>
  
  <hr>
  
  <p>TreeNode.java</p>
  
  <pre><code>public class TreeNode {
  
      private Object value;
      private TreeNode left, right;
  
      public TreeNode(Object value) {
          this.value = value;
          this.left = null;
          this.right = null;
      }
  
      public TreeNode(Object value, TreeNode left, TreeNode right) {
          this.value = value;
          this.left = left;
          this.right = right;
      }
  
      public void setValue(Object theNewValue) {
          value = theNewValue;
      }
  
      public void setLeft(TreeNode theNewLeft) {
          left = theNewLeft;
      }
  
      public void setRight(TreeNode theNewRight) {
          right = theNewRight;
      }
  
      public Object getValue() {
          return this.value;
      }
  
      public TreeNode getLeft() {
          return this.left;
      }
  
      public TreeNode getRight() {
          return this.right;
      }
  
  }
  </code></pre>
  
  <p>BinaryTree.java:</p>
  
  <pre><code>public abstract class BinaryTree {
  
      private TreeNode root;
  
      public BinaryTree() {
          this.root = null;
      }
  
      public void setRoot(TreeNode newNode) {
          this.root = newNode;
      }
  
      public TreeNode getRoot() {
          return this.root;
      }
  
      public boolean isEmpty() {
          return (this.root == null);
      }
  
      public abstract void insert(Comparable item);
      public abstract TreeNode find(Comparable key);
  
  } // end of class
  </code></pre>
  
  <p>CompleteTree.java:</p>
  
  <pre><code>public class CompleteTree extends BinaryTree {
  
      public CompleteTree() {
          super();
      }
  
      public void insert(Comparable item) {
          if(this.getRoot() == null) {
              this.setRoot(new TreeNode(item));
              return;
          }
  
          TreeNode t = this.getRoot();
          while(t != null) {
              if(t.getLeft() == null) {
                  t.setLeft(new TreeNode(item));
                  return;
              }
              else if(t.getRight() == null) {
                  t.setRight(new TreeNode(item));
                  return;
              }
              else {
                  int lCount = countChildren(t.getLeft());
                  int rCount = countChildren(t.getRight());
                  if(lCount == rCount)
                      t = t.getLeft();
                  else if(lCount == 0 || lCount == 1)
                      t = t.getLeft();
                  else
                      t = t.getRight();
              }
          }
      }
  
      public int countChildren(TreeNode t) {
          int count = 0;
          if(t.getLeft() != null)
              count++;
          if(t.getRight() != null)
              count++;
          return count;
      }
  
      public TreeNode find(Comparable key) {
          TreeNode p = this.getRoot();
          while(p != null &amp;&amp; key.compareTo(p.getValue()) != 0) {
              if(key.compareTo(p.getValue()) &lt; 0)
                  p = p.getLeft();
              else
                  p = p.getRight();
          }
          return p;
      }
  
      public BinaryTree swapSubtrees() {
          doSwap(this.getRoot());
          return this;
      }
  
      private void doSwap(TreeNode p) {
          if(p != null) {
              TreeNode temp = p.getLeft();
              p.setLeft(p.getRight());
              p.setRight(temp);
              doSwap(p.getLeft());
              doSwap(p.getRight());
          }
      }
  
      public void inorder() {
          doInorderTraversal(this.getRoot());
      }
  
      private void doInorderTraversal(TreeNode t) {
          if(t != null) {
              doInorderTraversal(t.getLeft());
              System.out.print(t.getValue() + " ");
              doInorderTraversal(t.getRight());
          }
      }
  
  }
  </code></pre>
  
  <p>CompleteTreeDemo.java:</p>
  
  <pre><code>public class CompleteTreeDemo {
  
      public static void main(String[] args) {
          CompleteTree tree = new CompleteTree();
          tree.insert(1);
          tree.insert(2);
          tree.insert(3);
          tree.insert(4);
          tree.insert(5);
          tree.insert(6);
          tree.insert(7);
          tree.insert(8);
          tree.insert(9);
          tree.insert(10);
          tree.insert(11);
          tree.insert(12); // This gets inserted into the wrong place
          tree.inorder();
      }
  
  }
  </code></pre>