title: If duplicate in BinarySearchTree is found entire child tree disappears?
body: <p><a href="https://stackoverflow.com/questions/34258971/checking-for-duplicate-values-in-binarysearchtree">This question does NOT answer my question so don't mark it duplicate</a></p>
  <p>When adding in this order:</p>
  <pre><code>        o.add(10);
          o.add(5);
          o.add(6);
          o.add(15);
          o.add(13);
          o.add(30);
          o.add(50);
          
          o.add(15);
  </code></pre>
  <p>I get this output:</p>
  <p><a href="https://i.stack.imgur.com/KBAVA.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/KBAVA.png" alt="enter image description here" /></a></p>
  <p>And in console:</p>
  <pre><code>is null 15
  not null 15
  </code></pre>
  <p>The size of the tree will still be 8. If they call add but a duplicate exist do nothing. There's obviously something in my searchAdd or add where I don't achieve this. Anyone can see where?
  I don't understand how the return can be null and not null at the same time...</p>
  <pre><code>import java.util.ArrayList;
  import java.util.Comparator;
  
  public class BinarySearchTree&lt;E&gt; implements Comparable&lt;E&gt; {
      BinaryNode&lt;E&gt; root; 
      int size;
      private Comparator&lt;E&gt; comparator;
      private ArrayList&lt;E&gt; sorted;
  
      public static void main(String args[]) {
          BinarySearchTree&lt;Integer&gt; o = new BinarySearchTree&lt;Integer&gt;();
  
          o.add(10);
          o.add(5);
          o.add(6);
          o.add(15);
          o.add(13);
          o.add(30);
          o.add(50);
  
          o.add(15);
  
          o.printTree();
          //BSTVisualizer t = new BSTVisualizer(&quot;Viz&quot;, 300, 300);
          //t.drawTree(o);
          System.out.println(o.size);
  
      }
  
      /**
       * Constructs an empty binary search tree.
       */
      public BinarySearchTree() {
          root = null;
          size = 0;
          comparator = (e1, e2) -&gt; ((Comparable&lt;E&gt;) e1).compareTo(e2);
      }
  
      @Override
      public int compareTo(Object o) {
          return 0;
      }
  
      /**
       * Inserts the specified element in the tree if no duplicate exists.
       * 
       * @param x element to be inserted
       * @return true if the the element was inserted
       */
      public boolean add(E x) {
          if (root == null) {
              root = new BinaryNode&lt;E&gt;(x);
              size++;
              return true;
          } else if (searchAdd(root, x) != null) {
              System.out.println(&quot;not null &quot; + x);
              size++;
              return true;
          } else {
              return false;
          }
      }
  
      private BinaryNode&lt;E&gt; searchAdd(BinaryNode&lt;E&gt; n, E x) {
          if (n == null) {
              return new BinaryNode&lt;E&gt;(x);
          } else {
              if (comparator.compare(x, n.element) == 0) {
                  System.out.println(&quot;is null &quot; + x);
                  return null;
              }else if (comparator.compare(x, n.element) &lt; 0) {
                  n.left = searchAdd(n.left, x);
                  return n;
              } else {
                  n.right = searchAdd(n.right, x);
                  return n;
              }
          }
      }
  
      public int size() {
          return size;
      }
  
      /**
       * Print tree contents in inorder.
       */
      public void printTree() {
          printTree(root);
      }
  
      private void printTree(BinaryNode&lt;E&gt; n) {
          if (n != null) {
              printTree(n.left);
              System.out.println(n.element);
              printTree(n.right);
          }
      }
  
      static class BinaryNode&lt;E&gt; {
          E element;
          BinaryNode&lt;E&gt; left;
          BinaryNode&lt;E&gt; right;
  
          private BinaryNode(E element) {
              this.element = element;
          }
      }
  
  }
  
  </code></pre>
  <p>Bad solution but solves it nonetheless.
  If size has increased then add returns true.</p>
  <pre><code>    public boolean add(E x) {
          int temp = size;
          if (root == null) {
              root = new BinaryNode&lt;E&gt;(x);
              size++;
              return true;
          } else {
              searchAdd(root, x);
              if(temp &lt; size) {
                  return true;
              }else {
                  return false;
              }
          }
      }
  
      private BinaryNode&lt;E&gt; searchAdd(BinaryNode&lt;E&gt; n, E x) {
          if (n == null) {
              size++;
              return new BinaryNode&lt;E&gt;(x);
          } else {
              if (comparator.compare(x, n.element) == 0) {
                  return n;
              }else if (comparator.compare(x, n.element) &lt; 0) {
                  n.left = searchAdd(n.left, x);
                  return n;
              } else {
                  n.right = searchAdd(n.right, x);
                  return n;
              }
          }
      }
  </code></pre>