title: How to make a Binary Search Tree a Complete Binary Search Tree in Java?
body: <p><strong>The accepted answer can make a Perfect tree (which is also a Complete tree). Although it cannot make a Complete tree without being Perfect. It was the closest answer to my request though. To make a compete the without being Perfect too, you could remove the rightmost leaves of the tree.</strong></p>
  
  <p><strong>1. Problem:</strong></p>
  
  <p>Trying to make a <code>Binary Search Tree</code> into a <code>Complete Binary Search Tree</code>. I can find lots of code examples for a <code>Complete Binary Tree</code>, but no <code>Complete Binary Search Tree</code>. The insert is working as a Binary Search Tree should. But this way of inserting is not a Complete Tree. If I add a bunch of random numbers, it will not be a Complete tree. How can I make the code insert to the tree <strong>but</strong> at the same time be a complete binary search tree?</p>
  
  <p>I would greatly appreciate a code example. I don't find it hard to understand it in theory at all, but very hard to implement it in code.  </p>
  
  <p><strong>2. What I tried:</strong></p>
  
  <ul>
  <li>To add the nodes in a level order way. </li>
  <li>While loop "Insert as long as the height is not 6 and all nodes are full nodes except leaves".</li>
  <li>"Add only to the right child if the value is greater than the parent and if the left child is not null".</li>
  <li><code>Arrays</code> and <code>LinkedLists</code> to add from.</li>
  </ul>
  
  <p><strong>3. How I insert:</strong></p>
  
  <pre><code>private BinaryNode&lt;AnyType&gt; insert( AnyType x, BinaryNode&lt;AnyType&gt; t )
  {
      if( t == null )
          return new BinaryNode&lt;&gt;( x, null, null);
  
      int compareResult = x.compareTo( t.element );
  
          if (compareResult &lt; 0)
              t.left = insert(x, t.left);
          else if (compareResult &gt; 0)
              t.right = insert(x, t.right);
          else
              ;  // Duplicate; do nothing
  
      return t;
  }
  </code></pre>
  
  <ul>
  <li>The <code>AnyType</code> is the value to be inserted, the <code>BinaryNode</code> is the
  current node.</li>
  </ul>
  
  <p><strong>4. What the program is able to do:</strong></p>
  
  <ul>
  <li>Insert and remove.</li>
  <li>Find Height, minimum, maximum or specific node.</li>
  <li>Preorder, Postorder, Levelorder, and Inorder searches.</li>
  <li>Get the number of full nodes, number of all nodes, and number of leaves.</li>
  </ul>
  
  <p><strong>5. Full program:</strong></p>
  
  <pre><code>import java.nio.BufferUnderflowException;
  import java.util.LinkedList;
  import java.util.Queue;
  import java.util.Random;
  
  /**
   * Implements an unbalanced binary search tree.
   * Note that all "matching" is based on the compareTo method.
   * @author Mark Allen Weiss
   */
  public class ExerciseBinarySearchTree03&lt;AnyType extends Comparable&lt;? super AnyType&gt;&gt;
  {
      /**
       * Construct the tree.
       */
      public ExerciseBinarySearchTree03( )
      {
          root = null;
      }
  
      public void preOrder(){
          System.out.println("\nPre Order ");
          preOrder(root);
      }
      public void postOrder(){
  
          System.out.println("\nPost Order ");
          postOrder(root);
      }
      public void inOrder(){
  
          System.out.println("\nIn Order ");
          inOrder(root);
      }
      public void levelOrder(){
          System.out.println("\nLevel Order ");
          levelOrder(root);
      }
  
  
      public int numberOfNodes(){
          return numberOfNodes(root);
      }
  
      public int numberOfFullNodes(){
          return numberOfFullNodes(root);
      }
      public int numberOfLeaves(){
          return numberOfLeaves(root);
      }
  
      /**
       * Insert into the tree; duplicates are ignored.
       * @param x the item to insert.
       */
      public void insert( AnyType x )
      {
          root = insert( x, root );
      }
  
      /**
       * Remove from the tree. Nothing is done if x is not found.
       * @param x the item to remove.
       */
      public void remove( AnyType x )
      {
          root = remove( x, root );
      }
  
      /**
       * Find the smallest item in the tree.
       * @return smallest item or null if empty.
       */
      public AnyType findMin( )
      {
          if( isEmpty( ) )
              throw new BufferUnderflowException( );
          return findMin( root ).element;
      }
  
      /**
       * Find the largest item in the tree.
       * @return the largest item of null if empty.
       */
      public AnyType findMax( )
      {
          if( isEmpty( ) )
              throw new BufferUnderflowException( );
          return findMax( root ).element;
      }
  
      /**
       * Find an item in the tree.
       * @param x the item to search for.
       * @return true if not found.
       */
      public boolean contains( AnyType x )
      {
          return contains( x, root );
      }
  
      /**
       * Make the tree logically empty.
       */
      public void makeEmpty( )
      {
          root = null;
      }
  
      /**
       * Test if the tree is logically empty.
       * @return true if empty, false otherwise.
       */
      public boolean isEmpty( )
      {
          return root == null;
      }
  
      /**
       * Print the tree contents in sorted order.
       */
      public void printTree( )
      {
          if( isEmpty( ) )
              System.out.println( "Empty tree" );
          else
              printTree( root );
      }
  
      /**
       * Internal method to insert into a subtree.
       * @param x the item to insert.
       * @param t the node that roots the subtree.
       * @return the new root of the subtree.
       */
      private BinaryNode&lt;AnyType&gt; insert( AnyType x, BinaryNode&lt;AnyType&gt; t )
      {
          if( t == null )
              return new BinaryNode&lt;&gt;( x, null, null);
  
          int compareResult = x.compareTo( t.element );
  
              if (compareResult &lt; 0)
                  t.left = insert(x, t.left);
              else if (compareResult &gt; 0)
                  t.right = insert(x, t.right);
              else
                  ;  // Duplicate; do nothing
  
          return t;
      }
  
      /* Given a binary tree, return true if the tree is complete
         else false */
      static boolean isCompleteBT(BinaryNode root)
      {
          // Base Case: An empty tree is complete Binary Tree
          if(root == null)
              return true;
  
          // Create an empty queue
          Queue&lt;BinaryNode&gt; queue =new LinkedList&lt;&gt;();
  
          // Create a flag variable which will be set true
          // when a non full node is seen
          boolean flag = false;
  
          // Do level order traversal using queue.
          queue.add(root);
          while(!queue.isEmpty())
          {
              BinaryNode temp_node = queue.remove();
  
              /* Check if left child is present*/
              if(temp_node.left != null)
              {
                  // If we have seen a non full node, and we see a node
                  // with non-empty left child, then the given tree is not
                  // a complete Binary Tree
                  if(flag == true)
                      return false;
  
                  // Enqueue Left Child
                  queue.add(temp_node.left);
              }
              // If this a non-full node, set the flag as true
              else
                  flag = true;
  
              /* Check if right child is present*/
              if(temp_node.right != null)
              {
                  // If we have seen a non full node, and we see a node
                  // with non-empty right child, then the given tree is not
                  // a complete Binary Tree
                  if(flag == true)
                      return false;
  
                  // Enqueue Right Child
                  queue.add(temp_node.right);
  
              }
              // If this a non-full node, set the flag as true
              else
                  flag = true;
          }
          // If we reach here, then the tree is complete Bianry Tree
          return true;
      }
  
  
  
  
  
  
  
  
  
  
  
  
      /**
       * Internal method to remove from a subtree.
       * @param x the item to remove.
       * @param t the node that roots the subtree.
       * @return the new root of the subtree.
       */
      private BinaryNode&lt;AnyType&gt; remove( AnyType x, BinaryNode&lt;AnyType&gt; t )
      {
          if( t == null )
              return t;   // Item not found; do nothing
  
          int compareResult = x.compareTo( t.element );
  
          if( compareResult &lt; 0 )
              t.left = remove( x, t.left );
          else if( compareResult &gt; 0 )
              t.right = remove( x, t.right );
          else if( t.left != null &amp;&amp; t.right != null ) // Two children
          {
              t.element = findMin( t.right ).element;
              t.right = remove( t.element, t.right );
          }
          else
              t = ( t.left != null ) ? t.left : t.right;
          return t;
      }
  
      /**
       * Internal method to find the smallest item in a subtree.
       * @param t the node that roots the subtree.
       * @return node containing the smallest item.
       */
      private BinaryNode&lt;AnyType&gt; findMin( BinaryNode&lt;AnyType&gt; t )
      {
          if( t == null )
              return null;
          else if( t.left == null )
              return t;
          return findMin( t.left );
      }
  
      /**
       * Internal method to find the largest item in a subtree.
       * @param t the node that roots the subtree.
       * @return node containing the largest item.
       */
      private BinaryNode&lt;AnyType&gt; findMax( BinaryNode&lt;AnyType&gt; t )
      {
          if( t != null )
              while( t.right != null )
                  t = t.right;
  
          return t;
      }
  
      /**
       * Internal method to find an item in a subtree.
       * @param x is item to search for.
       * @param t the node that roots the subtree.
       * @return node containing the matched item.
       */
      private boolean contains( AnyType x, BinaryNode&lt;AnyType&gt; t )
      {
          if( t == null )
              return false;
  
          int compareResult = x.compareTo( t.element );
  
          if( compareResult &lt; 0 )
              return contains( x, t.left );
          else if( compareResult &gt; 0 )
              return contains( x, t.right );
          else
              return true;    // Match
      }
  
      /**
       * Internal method to print a subtree in sorted order.
       * @param t the node that roots the subtree.
       */
      private void printTree( BinaryNode&lt;AnyType&gt; t )
      {
          if( t != null )
          {
              printTree( t.left );
              System.out.println( t.element );
              printTree( t.right );
          }
      }
  
      /**
       * Internal method to compute height of a subtree.
       * @param t the node that roots the subtree.
       */
      private int height( BinaryNode&lt;AnyType&gt; t )
      {
          if( t == null )
              return -1;
          else
              return 1 + Math.max( height( t.left ), height( t.right ) );
      }
  
  
      public int height(){
          return height(root);
      }
  
      private void preOrder(BinaryNode t )
      {
          if (t == null) {
              return;
          }
              System.out.println(t.element + " ");
              preOrder(t.left);
              preOrder(t.right);
  
      }
  
      private void postOrder(BinaryNode t){
          if (t == null) {
              return;
          }
              postOrder(t.left);
              postOrder(t.right);
              System.out.println(t.element + " ");
  
      }
  
      private void inOrder(BinaryNode t)
      {
          if (t == null) {
              return;
          }
              inOrder(t.left);
              System.out.println(t.element + " ");
              inOrder(t.right);
      }
  
      private void levelOrder(BinaryNode root) {
          if (root == null) {
              return;
          }
  
          Queue&lt;BinaryNode&gt; q = new LinkedList&lt;&gt;();
  
          // Pushing root node into the queue.
          q.add(root);
  
          // Executing loop till queue becomes
          // empty
          while (!q.isEmpty()) {
  
              BinaryNode curr = q.poll();
              System.out.print(curr.element + " ");
  
              // Pushing left child current node
                  if (curr.left != null) {
                      q.add(curr.left);
                  }
  
                  // Pushing right child current node
                  if (curr.right != null) {
                      q.add(curr.right);
                  }
              }
      }
  
      //O(n) for the below three methods.
      private int numberOfNodes(BinaryNode&lt;AnyType&gt; root){
          if ( root == null ) {
              return 0;
          }
          return 1 + numberOfNodes( root.left ) + numberOfNodes( root.right );
      }
  
  
      private int numberOfLeaves(BinaryNode&lt;AnyType&gt; t){
          if( t == null ) {
              return 0;
          }
          if( t.left == null &amp;&amp; t.right == null ) {
  
              return 1;
          }
              return numberOfLeaves(t.left) + numberOfLeaves(t.right);
      }
  
      private int numberOfFullNodes(BinaryNode&lt;AnyType&gt; root){
          if(root==null) {
              return 0;
          }
          if(root.left!=null &amp;&amp; root.right!=null) {
              return 1 + numberOfFullNodes(root.left) + numberOfFullNodes(root.right);
          }
          return numberOfFullNodes(root.left) + numberOfFullNodes(root.right);
      }
  
  
      // Basic node stored in unbalanced binary search trees
      private static class BinaryNode&lt;AnyType&gt;
      {
              // Constructors
          BinaryNode( AnyType theElement )
          {
              this( theElement, null, null );
          }
  
          BinaryNode( AnyType theElement, BinaryNode&lt;AnyType&gt; lt, BinaryNode&lt;AnyType&gt; rt )
          {
              element  = theElement;
              left     = lt;
              right    = rt;
          }
  
          AnyType element;            // The data in the node
          BinaryNode&lt;AnyType&gt; left;   // Left child
          BinaryNode&lt;AnyType&gt; right;  // Right child
      }
  
        /** The tree root. */
      private BinaryNode&lt;AnyType&gt; root;
  
  
      AnyType[] arr = (AnyType[]) new Integer[7];
  
  
      // Test program
      public static void main( String [ ] args ) {
          ExerciseBinarySearchTree03&lt;Integer&gt; bst = new ExerciseBinarySearchTree03&lt;&gt;( );
          final int NUMS = 20;
          final int GAP  =   37;
  
          System.out.println( "Checking... (no more output means success)" );
  
          bst.insert(10);
  
          for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS ) {
              if(i != 10) {
                  bst.insert(i);
              }
          }
  
          for( int i = 1; i &lt; NUMS; i+= 2 )
              bst.remove( i );
  
          if( NUMS &lt;= 40 )
              bst.printTree( );
          if( bst.findMin( ) != 2 || bst.findMax( ) != NUMS - 2 )
              System.out.println( "FindMin or FindMax error!" );
  
          for( int i = 2; i &lt; NUMS; i+=2 )
              if( !bst.contains( i ) )
                  System.out.println( "Find error1!" );
  
          for( int i = 1; i &lt; NUMS; i+=2 )
          {
              if( bst.contains( i ) )
                  System.out.println( "Find error2!" );
          }
  
          bst.inOrder();
      }
  
  
  }
  </code></pre>