title: How to delete a node in Binary Search Tree using Python
body: <pre><code>def delete_a_node(self,data):
      if self.root==None:
          print("Empty BST")
      else:
          parent=None
          node=self.root
          replace_node=None
          while(node!=None and node.data!=data):
              parent=node
              if data&gt;=node.data:
                  node=node.rightchild
                  flag=1
              else:
                  node=node.leftchild
                  flag=0
  
          if node is None:
              print("node not in BST.")
          else:
              if (node.leftchild==None) and (node.rightchild==None):
                  if (flag):
                      parent.rightchild=None
                  else:
                      parent.leftchild=None
                  del node
              elif (node.leftchild==None) or (node.rightchild==None):
                  if node.leftchild==None:
                      if(flag):
                          parent.rightchild=node.rightchild
                      else:
                          parent.leftchild=node.rightchild
                  else  :
                      if(flag):
                          parent.rightchild==node.leftchild
                      else:
                          parent.leftchild=node.leftchild
  
                  del node
  
  
              else:
                   replace_node,parent=self.minimum_element(node.rightchild)
                   node=replace_node
                   if parent==None:
                       node.rightchild=None
                   else:
                       parent.leftchild=None
                    del replace_node
  
  
  
  
  
  def minimum_element(self,node):
      if self.root==None:
          print("Empty BST")
      else:
          parent=None
          while(node.leftchild!=None):
              parent=node
              node=node.leftchild
          return (node,parent)
  </code></pre>
  
  <p>Hello guys, I was trying to delete a node from binary search tree.
  I tried to learn it from <a href="https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/" rel="nofollow noreferrer">https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/</a>. Since, they are using recursion in their code. I was unable to grasp it well.</p>
  
  <p>So, I tried to make this code.
  Here I initialize root in <strong>init</strong> method and rest two methods are in front of you.</p>
  
  <pre><code>  def __init__(self):
      self.root=None
  </code></pre>
  
  <p>FLAG Variable: I used it to just find the relationship between the parent node and data node(we want to delete).</p>
  
  <p>As we know, There are three cases</p>
  
  <ol>
  <li>When the node we want to delete has no child (it's  working fine)</li>
  <li>When the node we want to delete has one child (it's working fine)</li>
  <li>When the node we want to delete has both the children(<strong>HERE IS THE PROBLEM</strong>)</li>
  </ol>
  
  <p>Please, Can anyone help me with this code?</p>
  
  <p>Would you mind showing me,</p>
  
  <ol>
  <li>correct method to delete the node from BST</li>
  <li>should I use <strong>del node</strong> in python or not, because of I just read that there is no need to free up space in Python.</li>
  <li>Is my complexity too much comparing to <a href="https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/" rel="nofollow noreferrer">https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/</a> code?</li>
  </ol>
  
  <p>Output:</p>
  
  <p>bst.inorder()
  25--15--10--4--12--22--18--24--50--35--31--44--70--66--55--90--105--120--</p>
  
  <p>bst.delete_a_node(15)</p>
  
  <p>bst.inorder()
  25--15--10--4--12--22--18--24--50--35--31--44--70--66--55--90--105--120--</p>
  
  <p>Thank You in Advance :)</p>