title: Delete operation in Binary Search tree
body: <p>I have written this delete function to delete a node in a binary search tree. The problem is it deletes the root node of the key itself. Tried Debugging but not clear whats wrong with it.</p>
  <p>Also I don't understand why are we setting this <code>node-&gt;m_left=deletenode(data,node-&gt;m_left);</code></p>
  <pre><code>#include &quot;node.h&quot;
  #include &lt;queue&gt;
  
  template&lt;class T&gt;
  class bst
  {
  private:
      Node&lt;T&gt;* root;
  
  public:
      bst()
      {
          root = nullptr;
      }
  
      ~bst()
      {
          deletree(root);
      }
  
      Node&lt;T&gt;* gethead()
      {
          return this-&gt;root;
      }
  
      void addnode(Node&lt;T&gt;* node, T data)
      {
          if (this-&gt;root == nullptr) {
              Node&lt;T&gt;* new_node = new Node&lt;T&gt;(data);
              this-&gt;root = new_node;
          }
          else if (data &gt; node-&gt;m_data) {
              if (node-&gt;m_right != nullptr) {
                  addnode(node-&gt;m_right, data);
              }
              else {
                  Node&lt;T&gt;* new_node = new Node&lt;T&gt;(data);
                  node-&gt;m_right = new_node;
              }
          }
          else if (data &lt; node-&gt;m_data) {
              if (node-&gt;m_left != nullptr) {
                  addnode(node-&gt;m_left, data);
              }
              else {
                  Node&lt;T&gt;* new_node = new Node&lt;T&gt;(data);
                  node-&gt;m_left = new_node;
              }
          }
      }
  
      void addnode(T data)
      {
          addnode(this-&gt;root, data);
      }
  
      Node&lt;T&gt;* deletenode(T data, Node&lt;T&gt;* node)
      {
          //base case
          if (node == nullptr) {
              return nullptr;
          }
          if (data &lt; node-&gt;m_data) {
              node-&gt;m_left = deletenode(data, node-&gt;m_left);
          }
          if (data &gt; node-&gt;m_data) {
              node-&gt;m_right = deletenode(data, node-&gt;m_right);
          }
  
          if (node-&gt;m_left == nullptr &amp;&amp; node-&gt;m_right == nullptr) {
              node = nullptr;
          }
          return nullptr;
      }
  };
  </code></pre>