Assigning a base case when deleting a binary search tree

Question

I am taking a course in algorithms and data structures in Python 3, and my instructor recently introduced us to a binary search tree. However, it is difficult for me to understand the deletion algorithm. Below we introduced the implementation, however, when I originally wrote my own execution, I did not include the “base case”, and it still worked:

def remove(self, data): if self.root: self.root = self.remove_node(data, self.root) def remove_node(self, data, node): if node is None: return node if data < node.data: node.leftChild = self.remove_node(data, node.leftChild) elif data > node.data: node.rightChild = self.remove_node(data, node.rightChild) else: if not node.rightChild and not node.leftChild: print('removing leaf node') del node return None if not node.leftChild: print('removing node with single right child') tempNode = node.rightChild del node return tempNode elif not node.rightChild: print('removing node with single left child') tempNode = node.leftChild del node return tempNode print('removing node with two children') tempNode = self.get_predecessor(node.leftChild) node.data = tempNode.data node.leftChild = self.remove_node(tempNode.data, node.leftChild) return node 

Now all this makes sense to me, except for the instructions below:

 if node is None: return node 

When we learned about the basic cases, we were taught that they are essentially the exit points for our algorithms. However, I do not understand how this takes place in this code. Firstly, I don’t see how a node can be empty, and even if that were the case, why would we return an empty node? As far as I can see, this check makes no sense in general recursion, because we do not seem to “repeat it” like in any other recursive function. I would really appreciate an explanation!

Answer 1

The base case (s) generally serve one or more purposes, including:

• preventing infinite recursion of a function
• Function error prevention in case of errors in corner cases
• calculate / return value / result to callers above in the recursion tree

When deleting a tree, the first point is not a problem (because the recursion tree will have only a finite number of nodes - the same as the tree that you are recursing). You will be concerned about points 2 and 3 here.

In your function, you have a basic case - in fact you have two (thanks to @ user2357112) -

• Not found part indicated

   if node is None: return node 

  and

• The part of the found value indicated by your code inside the else that performs the actual deletion.

To make the behavior consistent with recursive cases, the base case, which is independent of the value, returns None . As you can see, the first base case is consistent, performs the second function of the general base case described above, while the second base case performs the third.