title: C++ delete min element in binary tree
body: <p>I have the following function for deleting the min element:</p>
  
  <pre><code>int BinaryTree::delete_min_helper(TreeNode *node){
  
     while(node-&gt;left != NULL){
       node = node-&gt;left;
     }
  
     if(node == root){
       return 1;
     }
  
     delete node;
     node = NULL;
     return 0;
  }
  </code></pre>
  
  <p>I always pass a pointer to the root node to this function.  I've tried this and a few variations of it, but it always seems to delete the the wrong thing or not delete anything at all.  Any ideas why?</p>
  
  <p>Here is a compilable example:</p>
  
  <pre><code>#ifndef _TREE_H_
  #define _TREE_H_
  
  #include &lt;stdlib.h&gt;
  #include &lt;stdio.h&gt;
  #include &lt;string.h&gt;
  
  struct TreeNode {
    int val;
    char *str;
    TreeNode *left;
    TreeNode *right;
  };
  
  class BinaryTree {
    public:
  
   BinaryTree();
   ~BinaryTree();
  
   int insert_node(unsigned int val, char *str);
   TreeNode *find_min();
   int delete_min();
   void print();
  
   private:
  
   int insert_node_helper(TreeNode *&amp;node, unsigned int val, char *str);
   int delete_min_helper(TreeNode *node);
   void print_helper(TreeNode *node);
  
   TreeNode *root;  
  };
  
  #endif
  
  BinaryTree::BinaryTree(){
    this-&gt;root = NULL;
  }
  
  
  BinaryTree::~BinaryTree(){
  }
  
  int BinaryTree::insert_node(unsigned int val, char *str){
    return insert_node_helper(this-&gt;root, val, str);
  }
  
  int BinaryTree::insert_node_helper(TreeNode *&amp;node, unsigned int val, char *str){
  
    if(node == NULL){
      node = new TreeNode;
      node-&gt;val = val;
      node-&gt;str = strdup(str);
      node-&gt;left = NULL;
      node-&gt;right = NULL;
      if(node != NULL){
        return 0;
      }else{
        puts("inserted null node");
        return 1;
     }
   }else if(val &lt;= node-&gt;val){
     return insert_node_helper(node-&gt;left, val, str);
   }else if(val &gt; node-&gt;val){
     return insert_node_helper(node-&gt;right, val, str);
   }
  
   return 1;
  }
  
  void BinaryTree::print(){
    print_helper(this-&gt;root);
  }
  
  
  void BinaryTree::print_helper(TreeNode *node){
  
      if(node != NULL){
        print_helper(node-&gt;right);
        printf("%d occurrences of \"%s\"\n", node-&gt;val, node-&gt;str);
        print_helper(node-&gt;left);
      }
  
  }
  
  TreeNode *BinaryTree::find_min(){
    TreeNode *temp = this-&gt;root;
    while(temp-&gt;left != NULL){
      temp = temp-&gt;left;
    }
    return temp;
  }
  
  int BinaryTree::delete_min(){
     return delete_min_helper(root);
  }
  
  int BinaryTree::delete_min_helper(TreeNode *node){
  
     while(node-&gt;left != NULL){
       node = node-&gt;left;
     }
  
    if(node == root){
      puts("attempted to delete root");
      return 1;
    }
  
    delete node;
    node = NULL;
    return 0;
  }
  
  #include &lt;time.h&gt;
  
  int main(){
  
    BinaryTree bt;
  
    srand(time(NULL));
    for(int i = 0; i &lt; 10; i++){
       bt.insert_node(rand() % 20, "test");
    }
  
    bt.print();
    printf("min val = %d\n", bt.find_min()-&gt;val);
    puts("#################################");
    bt.delete_min();
    bt.print();
    printf("min val = %d\n", bt.find_min()-&gt;val);
  
    return 0;
  }
  </code></pre>