title: Binary Search Tree Recursive Delete
body: <p>I'm working on Binary Search Trees, and currently working on recursive delete method. I have a bug in my code; it deletes nodes with no children and with one-child. Problem arises when trying to delete node with two children. (Point of reference - I am replacing deleted node with smallest node in Right Subtree)</p>
  
  <p>My code is:</p>
  
  <pre><code>//Driver
  public void delete (String val){
  root = delete(root, val);
  }
  
  //Recursive Delete Method   
  private static StringNode delete(StringNode node, String v){
          StringNode temp;
          if(node == null){
              return null;
          }
          if(v.compareTo(node.getString()) &lt; 0){
              node.setLeft(delete(node.getLeft(), v));
          }
          else if(v.compareTo(node.getString()) &gt; 0){
              node.setRight(delete(node.getRight(), v));
          }
          else{
              if(node.getLeft() == null){
                  node = node.getRight();
              }
              else if(node.getRight() == null){
                  node = node.getLeft();
              }
              else{
                  node = node.getRight();
                  while(node.getLeft() != null){
                      node = node.getLeft();
                  }
                  node.setRight(delete(node, node.getString()));
              }
          }
          return node;
      }
  </code></pre>
  
  <p>I have debugged and see that I lose a child when re-connecting the nodes after deletion.  But I don't know how to correct in my code.</p>