title: Remove method binary search tree
body: <p>I am trying to implement a remove method for the BST structure that I have been working on. Here is the code with find, insert, and remove methods:</p>
  
  <pre><code>public class BST {
      BSTNode root = new BSTNode("root");
  
      public void insert(BSTNode root, String title){
          if(root.title!=null){
  
              if(title==root.title){
                  //return already in the catalog
              }
              else if(title.compareTo(root.title)&lt;0){
  
                  if(root.leftChild==null){
                      root.leftChild = new BSTNode(title);
                  }
                  else{
                      insert(root.leftChild,title);
                  }
              }
              else if(title.compareTo(root.title)&gt;0){
                  if(root.rightChild==null){
                      root.rightChild = new BSTNode(title);
                  }
                  else{
                      insert(root.rightChild,title);
                  }
              }
          }
      }
  
      public void find(BSTNode root, String title){
          if(root!= null){
              if(title==root.title){
                  //return(true);
              }
              else if(title.compareTo(root.title)&lt;0){
                  find(root.leftChild, title);
              }
              else{
                  find(root.rightChild, title);
              }
          }
          else{
              //return false;
          }
      }
  
      public void remove(BSTNode root, String title){
          if(root==null){
              return false;
          }
          if(title==root.title){
              if(root.leftChild==null){
                  root = root.rightChild;
              }
              else if(root.rightChild==null){
                  root = root.leftChild;
              }
              else{
                  //code if 2 chlidren remove
              }
          }
          else if(title.compareTo(root.title)&lt;0){
              remove(root.leftChild, title);
          }
          else{
              remove(root.rightChild, title);
          }
      }
  }
  </code></pre>
  
  <p>I was told that I could use the insert method to help me with the remove method, but I am just not seeing how I can grab the smallest/largest element, and then replace the one I am deleting with that value, then recursively delete the node that I took the replacement value, while still maintaining O(logn) complexity. Anyone have any ideas or blatant holes I missed, or anything else helpful as I bang my head about this issue?</p>
  
  <p>EDIT:
  I used the answers ideas to come up with this, which I believe will work but I'm getting an error that my methods (not just the remove) must return Strings, here is what the code looks like, I thought that's the return statements??</p>
  
  <pre><code>public String remove(BSTNode root, String title){
              if(root==null){
                  return("empty root");
              }
              if(title==root.title){
                      if(root.leftChild==null){
                              if(root.rightChild==null){
                                      root.title = null;
                                      return(title+ "was removed");
                              }
                              else{
                              root = root.rightChild;
                              return(title+ "was removed");
                              }
                      }
                      else if(root.rightChild==null){
                              root = root.leftChild;
                              return(title+ "was removed");
                      }
                      else{
                              String minTitle = minTitle(root);
                              root.title = minTitle;
                              remove(root.leftChild,minTitle);
                              return(title+ "was removed");
                      }
              }
              else if(title.compareTo(root.title)&lt;0){
                      remove(root.leftChild, title);
              }
              else{
                      remove(root.rightChild, title);
              }
      }
  </code></pre>