title: delete Binary Search Tree
body: <p>I try to delete the node of Binary Search Tree
  The outcome I've gotten when I print out is actually None
  This deletion, actually can delete anything key from the binary tree itself.</p>
  
  <p>I'm new to Binary Search Tree.
  Can someone help me out with my code?
  You help will be apprieciated.</p>
  
  <p>Thanks</p>
  
  <pre><code>def deleteMin(self):
      self.root = self.deleteMin2(self.root)
  
  def deleteMin2(self, node):
      if node.left is None:
          return node.right
      node.left = self.deleteMin2(node.left)
      node.count = 1 + self.size2(node.left) + self.size2(node.right)
      return node
  
  def delete(self,key):
      self.root = self.delete2(self.root,key)
  
  def delete2(self,node,key):
      if node is None:
          return None
      if key &lt; node.key:
          node.left = self.delete2(node.left,key)
      elif(key &gt; node.key):
          node.right = self.delete2(node.right,key)
      else:
          if node.right is None:
              return node.left
          if node.left is None:
              return node.right
          t = node
          node = self.min(t.right)
          node.right = self.deleteMin2(t.right)
          node.left = t.left
      node.count = self.size2(node.left) + self.size2(node.right) + 1
      return node
  </code></pre>
  
  <p>Full Code</p>
  
  <pre><code>import os
  import pygraphviz as pgv
  from collections import deque
  
  
  class BST:
      root=None
  
      def put(self, key, val):
          self.root = self.put2(self.root, key, val)
  
      def put2(self, node, key, val):
          if node is None:
              #key is not in tree, create node and return node to parent
              return Node(key, val)
          if key &lt; node.key:
              # key is in left subtree
              node.left = self.put2(node.left, key, val)
          elif key &gt; node.key:
              # key is in right subtree
              node.right = self.put2(node.right, key, val)
          else:
              node.val = val
          node.count = 1 + self.size2(node.left) + self.size2(node.right)
          return node
  
  
  
  
      # draw the graph
      def drawTree(self, filename):
          # create an empty undirected graph
          G=pgv.AGraph('graph myGraph {}')
  
          # create queue for breadth first search
          q = deque([self.root])
          # breadth first search traversal of the tree
          while len(q) &lt;&gt; 0:
              node = q.popleft()
              G.add_node(node, label=node.key+":"+str(node.val))
              if node.left is not None:
                  # draw the left node and edge
                  G.add_node(node.left, label=node.left.key+":"+str(node.left.val))
                  G.add_edge(node, node.left)
                  q.append(node.left)
              if node.right is not None:
                  # draw the right node and edge
                  G.add_node(node.right, label=node.right.key+":"+str(node.right.val))
                  G.add_edge(node, node.right)
                  q.append(node.right)
  
          # render graph into PNG file
          G.draw(filename,prog='dot')
          os.startfile(filename)
  
      def createTree(self):
          #root
          self.put("F",6)
          self.put("D",4)
          self.put("C",3)
          self.put("B",2)
          self.put("A",1)
          self.put("E",5)
          self.put("I",9)
          self.put("G",7)
          self.put("H",8)
          self.put("J",10)
  
     def get(self,key):
          temp = self.root
          while temp is not None:
              #if what you are searching for is the root
              if temp.key == key:
                  return temp.val
              #if it's not the root
              #check to see if what you're searching for is less than the root key
              #if so, search left
              elif temp.key &gt; key:
                  temp = temp.left
              #else search right
              else:
                  temp = temp.right
          return None
  
  
  
      def size(self,key):
          node = self.root
          #if root is not none
          while node is not None:
          #if the given node is the current node
              if node.key == key:
                  #return itself
                  return self.size2(node)
          #if the node that you are at is smaller than root
              elif node.key &gt; key:
                  node = node.left
              else:
                  node = node.right
  
      def size2(self,n):
          #if node is none
          if n is None:
              #return 0
              return 0
          else:
              #else track
              return n.count
  
      def depth(self, key):
          return self.depth2(self.root, key)
  
      def depth2(self, root, key, current_depth=0):
          #if given node is not in the tree
          if not root:
              return -1
          #inspect given key against current node (root)
          #if current node and given node is match
          elif root.key == key:
              return current_depth
          #if given node is less than current node
          elif key &lt; root.key:
              return self.depth2(root.left, key, current_depth + 1)
          else:
              return self.depth2(root.right, key, current_depth + 1)
  
  
      def height(self,key):
          node = self.root
          #if root is not none
          while node is not None:
          #if what you are searching for is the root
              if node.key == key:
                  #return itself
                  return self.height2(node)
          #if the node that you are at is smaller than root
              elif node.key &gt; key:
                  node = node.left
              else:
                  node = node.right
  
  
      def height2(self,n):
          if n is None:
              return -1
          else:
              #return the max
              return  1 + max(self.height2(n.left),self.height2(n.right))
  
  
      def inOrder(self,n):
          if n is None:
              return 0
          else:
              self.inOrder(n.left)
              print n.key , ": " , n.val;
              self.inOrder(n.right)
  
      def preOrder(self,n):
          if n is None:
              return 0
          else:
              print n.key , ": " , n.val;
              self.preOrder(n.left)
              self.preOrder(n.right)
  
      def postOrder(self,n):
          if n is None:
              return 0
          else:
              self.postOrder(n.left)
              self.postOrder(n.right)
              print n.key , ": " , n.val;
  
  # ------------------------------------------------------------------------
      def deleteMin(self):
          self.root = self.deleteMin2(self.root)
  
      def deleteMin2(self, node):
          if node.left is None:
              return node.right
          node.left = self.deleteMin2(node.left)
          node.count = 1 + self.size2(node.left) + self.size2(node.right)
          return node
  
      def delete(self,key):
          self.root = self.delete2(self.root,key)
  
      def delete2(self,node,key):
          if node is None:
              return None
          if key &lt; node.key:
              node.left = self.delete2(node.left,key)
          elif(key &gt; node.key):
              node.right = self.delete2(node.right,key)
          else:
              if node.right is None:
                  return node.left
              if node.left is None:
                  return node.right
              t = node
              node = self.min(t.right)
              node.right = self.deleteMin2(t.right)
              node.left = t.left
          node.count = self.size2(node.left) + self.size2(node.right) + 1
          return node
  
  
  class Node:
      left = None
      right = None
      key = 0
      val = 0
      count = 0
  
  
  
      def __init__(self, key, val):
          self.key = key
          self.val = val
          self.count += 1
  
  
  
  
  bst = BST()
  bst.createTree()
  bst.drawTree("demo.png")
  node = bst.root
  print "Get: " , bst.get("C") , "\n"
  print "Size: ", bst.size("D"), "\n"
  print "Depth:", bst.depth("B"), "\n"
  print "Height:", bst.height("B"), "\n"
  print "\n In Order"
  bst.inOrder(node)
  print "\n Pre Order \n"
  bst.preOrder(node)
  print "\n Post Order \n"
  bst.postOrder(node)
  
  
  node = bst.root
  print  bst.delete(node)
  </code></pre>