title: Deleting nodes in a binary search tree in python?
body: <p>so I'm stuck on a question in my computer science class, it asks for me to extend our previously written binary search tree class, and add a way to delete nodes from the tree, this will have to take into consideration if that node has 0, 1, or 2 children. After looking over the conditions and stuff I concluded that I would need to find the parent of the specified node in order to do this, since the the children of the deleted node will be assigned to the parent.
  This is where I'm stuck, since we just recently started on nodes and linked lists I'm still fairly new to this, which is why I have no clue on how to keep track of the parent node.</p>
  
  <p>This is the code for the BST class:</p>
  
  <p>import copy</p>
  
  <pre><code>class _BSTNode:
  
      def __init__(self, value):
          """
          -------------------------------------------------------
          Creates a node containing a copy of value.
          Use: node = _BSTNode( value )
          -------------------------------------------------------
          Preconditions:
            value - data for the node (?)
          Postconditions:
            Initializes a BST node containing value. Child pointers are None, height is 1.
          -------------------------------------------------------
          """
          self._value = copy.deepcopy(value)
          self._left = None
          self._right = None
          self._height = 1
          return
  
      def _update_height(self):
          """
          -------------------------------------------------------
          Updates the height of the current node.
          Use: node._update_height()
          -------------------------------------------------------
          Postconditions:
            _height is 1 plus the maximum of the node's (up to) two children.
          -------------------------------------------------------
          """
          if self._left is None:
              left_height = 0
          else:
              left_height = self._left._height
  
          if self._right is None:
              right_height = 0
          else:
              right_height = self._right._height
  
          self._height = max(left_height, right_height) + 1
          return
  
      def __str__(self):
          """
          -------------------------------------------------------
          DEBUG: Prints node height and value.
          -------------------------------------------------------
          """
          return "h: {}, v: {}".format(self._height, self._value)
  </code></pre>
  
  <p>&nbsp;</p>
  
  <pre><code>class BST:
  
      def __init__(self):
          """
          -------------------------------------------------------
          Initializes an empty BST.
          Use: bst = BST()
          -------------------------------------------------------
          Postconditions:
            Initializes an empty bst.
          -------------------------------------------------------
          """
          self._root = None
          self._count = 0
          return
  
      def is_empty(self):
          """
          -------------------------------------------------------
          Determines if bst is empty.
          Use: b = bst.is_empty()
          -------------------------------------------------------
          Postconditions:
            returns:
            True if bst is empty, False otherwise.
          -------------------------------------------------------
          """
          return self._root is None
  
      def __len__(self):
          """
          -------------------------------------------------------
          Returns the number of nodes in the BST.
          Use: n = len( bst )
          -------------------------------------------------------
          Postconditions:
            returns:
            the number of nodes in the BST.
          -------------------------------------------------------
          """
          return self._count
  
      def insert(self, value):
          """
          -------------------------------------------------------
          Inserts a copy of value into the bst.
          Use: b = bst.insert( value )
          -------------------------------------------------------
          Preconditions:
            value - data to be inserted into the bst (?)
          Postconditions:
            returns:
            inserted - True if value is inserted into the BST,
            False otherwise. Values may appear only once in a tree. (bool)
          -------------------------------------------------------
          """
          self._root, inserted = self._insert_aux(self._root, value)
          return inserted
  
      def _insert_aux(self, node, value):
          """
          -------------------------------------------------------
          Inserts a copy of _value into node.
          Private recursive operation called only by insert.
          Use: node, inserted = self._insert_aux( node, value )
          -------------------------------------------------------
          Preconditions:
            node - a bst node (_BSTNode)
            value - data to be inserted into the node (?)
          Postconditions:
            returns:
            node - the current node (_BSTNode)
            inserted - True if value is inserted into the BST,
            False otherwise. Values may appear only once in a tree. (boolean)
          -------------------------------------------------------
          """
          if node is None:
              # Base case: add a new node containing the value.
              node = _BSTNode(value)
              self._count += 1
              inserted = True
          elif value &lt; node._value:
              # General case: check the left subtree.
              node._left, inserted = self._insert_aux(node._left, value)
          elif value &gt; node._value:
              # General case: check the right subtree.
              node._right, inserted = self._insert_aux(node._right, value)
          else:
              # Base case: value is already in the BST.
              inserted = False
  
          if inserted:
              # Update the current node height if any of its children have been changed.
              node._update_height()
          return node, inserted
  
      def retrieve(self, key):
          """
          -------------------------------------------------------
          Retrieves a copy of a value matching key in a BST. (Iterative)
          Use: v = bst.retrieve( key )
          -------------------------------------------------------
          Preconditions:
            key - data to search for (?)
          Postconditions:
            returns:
            value - value in the node containing key, otherwise None (?)
          -------------------------------------------------------
          """
          node = self._root
          value = None
  
          while node is not None and value is None:
  
              if key &lt; node._value:
                  node = node._left
              elif key &gt; node._value:
                  node = node._right
              else:
                  value = copy.deepcopy(node._value)
          return  value
  
      def inorder(self):
          """
          -------------------------------------------------------
          Prints the contents of the tree in inorder order.
          -------------------------------------------------------
          Postconditions:
            The contents of the tree are printed inorder.
          -------------------------------------------------------
          """
          if self._root is not None:
              self._inorder_aux(self._root)
          return
  
      def _inorder_aux(self, node):
          """
          -------------------------------------------------------
          Prints the contents of the subtree at node.
          -------------------------------------------------------
          Preconditions:
            node - a bst node (_BSTNode)
          Postconditions:
            prints:
            the values at the subtree of node in inorder
          -------------------------------------------------------
          """
          if node._left is not None:
              self._inorder_aux(node._left)
          print(node._value)
          if node._right is not None:
              self._inorder_aux(node._right)
  
          return
  
      def postorder(self):
          """
          -------------------------------------------------------
          Prints the contents of the tree in postorder order.
          -------------------------------------------------------
          Postconditions:
            The contents of the tree are printed postorder.
          -------------------------------------------------------
          """
          if self._root is not None:
              self._postorder_aux(self._root)
          return
  
      def _postorder_aux(self, node):
          """
          -------------------------------------------------------
          Prints the contents of the subtree at node.
          -------------------------------------------------------
          Preconditions:
            node - a bst node (_BSTNode)
          Postconditions:
            prints:
            the values at the subtree of node in postorder
          -------------------------------------------------------
          """
          if node._left is not None:
              self._preorder_aux(node._left)
          if node._right is not None:
              self._preorder_aux(node._right)
          print(node._value)
  
  
          return
  
      def preorder(self):
          """
          -------------------------------------------------------
          Prints the contents of the tree in preorder order.
          -------------------------------------------------------
          Postconditions:
            The contents of the tree are printed preorder.
          -------------------------------------------------------
          """
          if self._root is not None:
              self._preorder_aux(self._root)
          return
  
      def _preorder_aux(self, node):
          """
          -------------------------------------------------------
          Prints the contents of the subtree at node.
          -------------------------------------------------------
          Preconditions:
            node - a bst node (_BSTNode)
          Postconditions:
            prints:
            the values at the subtree of node in preorder
          -------------------------------------------------------
          """
  
          print(node._value)
          if node._left is not None:
              self._postorder_aux(node._left)
          if node._right is not None:
              self._postorder_aux(node._right)
          return
  
  
      def traverse(self):
          """
          ---------------------------------------------------------
          Returns the contents of bst in an array in sorted order.
          ---------------------------------------------------------
          Postconditions:
            returns:
            a - an array containing the contents of bst in sorted order.
          ---------------------------------------------------------
          """
          a = []
          self._traverse_aux(self._root, a)
          return a
  
      def _traverse_aux(self, node, a):
          """
          ---------------------------------------------------------
          Traverse the node's subtree in inorder, adding the contents of
          each node to an array
          ---------------------------------------------------------
          Preconditions:
            node - the root of a subtree (_BSTNode)
          Postconditions:
            a - contains the contents of the subtree of node 
                      in sorted order.
          ---------------------------------------------------------
          """
          if node._left is not None:
              self._traverse_aux(node._left, a)
          a.append(node._value)
          if node._right is not None:
              self._traverse_aux(node._right, a)
  
  
          return
  
      def is_identical(self, rhs):
          """
          ---------------------------------------------------------
          Determines whether two BSTs are identical.
          Use: b = bst.is_identical( rhs )
          -------------------------------------------------------
          Preconditions:
            rhs - another bst (BST)
          Postconditions:
            returns:
            identical - True if this bst contains the same values
            in the same order as rhs, otherwise returns False.
          -------------------------------------------------------
          """
          identical = self._is_identical_aux(self._root, rhs._root)
          return identical
  
      def _is_identical_aux(self, node1, node2):
          """
          ---------------------------------------------------------
          Determines whether two subtrees are identical.
          Use: b = bst.is_identical( node1, node2 )
          -------------------------------------------------------
          Preconditions:
            node1 - node of the current BST (_BSTNode)
            node2 - node of the rhs BST (_BSTNode)
          Postconditions:
            returns:
            result - True if this stubtree contains the same values as rhs
            subtree in the same order, otherwise returns False.
          -------------------------------------------------------
          """
          result = True
          if node1._value != node2._value:
              result = False
          if node1._left is not None and node2._left is not None and result == True:
              result = self._is_identical_aux(node1._left, node2._left)
          if node1.right is not None and node2._right is not None and result == True:
              result = self._is_identical_aux(node1._right, node2._right) 
  
  
  
          return result
  
      def leaf_count(self):
          """
          ---------------------------------------------------------
          Returns the number of leaves (nodes with no children) in bst.
          Use: n = bst.leaf_count()
          (Recursive algorithm)
          ---------------------------------------------------------
          Postconditions:
            returns:
            n - number of nodes with no children in bst.
          ---------------------------------------------------------
          """
          n = self._leaf_count_aux(self._root)
          return n
  
      def _leaf_count_aux(self, node):
          """
          ---------------------------------------------------------
          Returns the number of leaves (nodes with no children) in bst.
          Use: n = bst.leaf_count()
          (Recursive algorithm)
          ---------------------------------------------------------
          Preconditions:
            node - a BST node (_BSTNode)
          Postconditions:
            returns:
            n - number of nodes with no children below node.
          ---------------------------------------------------------
          """
          count = 0
          if node._left is None and node._right is None:
              count += 1
          if node._left is not None and node._right is None:
              count += self._leaf_count_aux(node._left)
          if node._left is None and node._right is not None:
              count += self._leaf_count_aux(node._right)
          if node._left is not None and node._right is not None:
              count += self._leaf_count_aux(node._left)
              count += self._leaf_count_aux(node._right)
  
  
          return count
      def _delete_node(self, node):
          """
          -------------------------------------------------------
          Removes a node from the bst.
          Use: node = self._delete_node(node)
          -------------------------------------------------------
          Preconditions:
            node - the bst node to be deleted (_BSTNode)
          Postconditions:
            returns:
            node - the node that replaces the deleted node. This node is the node
            with the maximum value in the current node's left subtree (_BSTNode)
          -------------------------------------------------------
          """
  
          # Your code here.
  
          return node
  
      def parent_i(self, key):
          """
          ---------------------------------------------------------
          Returns the value of the parent node of a key node in a bst.
          ---------------------------------------------------------
          Preconditions:
            key - a key value (?)
          Postconditions:
            returns:
            value - a copy of the value in a node that is the parent of the
            key node, None if the key is not found.
          ---------------------------------------------------------
          """
  
          # Your code here
  
          return value
  </code></pre>
  
  <p>The last two functions in the BST class, parent_i and _delete_node is what I'm trying to write, the comments are the conditions my teachers have written for those functions we need to write. I think if I find a way to get the parent then the deletion function should be easy to do, but for now I have no idea where to start. Help will be very much appreciated! Also the few functions in the middle like min_i and max_i is supposed to be that way, probably for a future assignment or lab in our class for us to write.</p>
  
  <p>Thanks in advance!</p>
  
  <p>edit: ok so I understand the structure now, but now I'm confused as to what if I try to remove a node with 2 children, and the higher one of the 2 children also has 2 children, and so on? what should I do for this to work for all bsts of all sizes?</p>