Finally Understanding: Recursion and Binary Search Trees

15 min readMay 15, 2018

Hi guys, my name is Sid, and like you, I am a computer science enthusiast. This is my first tutorial in data structures. Today, I want to go over a popular data structure, known as the Binary Search Tree, or BST. To first understand this structure, we must first understand a key concept in math, art, and computer science, known as recursion.

What is Recursion?

First, we see how a computer manages the things it has to do in order, using a data structure known as a stack.

Let’s start out with an example. Below I have a program that creates a function called printHello(), which just returns the second function created, hello(). In the last line of this script, the function ‘printHello()’ is CALLED. And this my friends, activates the call stack of the program. According to our program, the first thing that our program must do is return printhello(), becaused it was called first. So we go throught the function step by step.

def printHello():
    return hello()
def hello():
    return "Hello"
printHello()

What printHello() is telling the computer to do now is to return the function hello(). And this causes our list of priorities to change. In order to complete printHello(), we have to complete the function hello(). This adds a new stack to our call stack. Previously, the top stack on the call stack was the printHello() function.

Now we jump into the function hello(). What this function does is it RETURNS the string ‘Hello’. Thats it. This function has done what it has to do, which was return a value for the stack below it, or in other words give something for the printHello() function to return. And voila, our program is finally complete and it returns the string ‘Hello’, and like that we ‘pop’ all of the layers in our call stack.

This example explains HALF of what recursion is. Now it is time to delve into the other half. Recursion basically means when a function CALLS ITSELF. We understand what it means to call a function, but what happens when a function calls itself? We will explain this using a famous example, known as calculating the factorial of a number. The factorial of a number is when you multiply a number with all the numbers below it. It looks something like this:

This is the factorial of the number 5, which computes to 120

But wait !? Isn’t the factorial of 5 basically multiplying 5 by the factorial of 4? And that is absolutely right. What the expression above is basically this. And now this is where we solve the factorial of 5 recursively using our call stack:

Why did we stop at factorial of 1? Well, the factorial of 1 is 1. In recursive programs, this is often known as the BASE CASE. The base case is basically a parameter, or input you pass into the function, which is always true or trivial. Now that we know the factorial of 1, we can ‘pop’ this call stack. And so we find out that the factorial of 5 is 120. I have also written a snippet of code which you can try out.

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)
factorial(5)

From these two examples, you should now be able to gain an understanding of recursion. Recursion is a really useful tool, as it lets us solve big problems as a bunch of ‘sub-problems’. Recursion is a tool that is used a lot in Divide and Conquer programming paradigms, which we will see in the future. Now let’s talk about Binary Search Trees.

Binary Search Tree (BST)

A binary search tree is a data structure that serves as a collection of nodes. A node is an object that has three attributtes. They are:

The data: A variable that stores the data in the node ie, a number
Left connection: A variable that can store another node
Right connection: A variable that can store another node

These nodes can then be arranged to form a Binary Search Tree, a collection of nodes:

Since each node is an ‘object’, we can create a class for the node. Below is the implementation for the Node we will be using throughout this tutorial. As you can see, each node initializes itself with a value (data), and sets it’s left and right childs as None FOR THE TIME BEING. The first node of a tree is called the ROOT node. If you notice, the tree data structure looks like an upside down tree. That is why this node is called the root. In the case of the tree above, the root node is 8.

class Node:
    def __init__(self, val):
        self.data = val
        self.left = None
        self.right = None

Now you may be asking yourself, why did we learn about recursion in order to learn about trees? Well, this is because a tree is what I call a recursive data structure. What do I mean by this? Look at the trees below. They are the same tree. Remember how we defined recursion as solving sub problems of a bigger problem. Look at the tree on the right. It looks like a tree, made up of smaller subtrees, and those sub-trees are also made up of sub-trees. And that is why recursion is so important when understanding trees. Eventually, recursively, we get to a point where the ‘sub trees’ are just nodes. which is why the node is so important in the tree as well.

Now lets look at one of the methods used in BST’s, called insertion.

Insertion

The first method of the Binary Search Tree that we will be discussing about is how to insert nodes. One of the key things about the binary search tree that makes it so speacial is that the LEFT CHILD of every node is LESS than or equal to the data in the ROOT node, and the RIGHT CHILD of every node is greater than the data in the root node. We organize the nodes in this way because it will allow us to do something pretty useful, which we will see in the next sections.

If every node can only have two children, and we want to INSERT another node, what do we do? We use recursion.

If we encounter a value that is LESS than the root node, we travel down to the LEFT child of the root node and compare with the data stored in that node. Again, if the value is less than the current node, we go left, else we go right, UNTIL we encounter a situation where we have to go left or right and there IS NO CHILD, or the left/right node of the current node is set to None. That is where we wil create a new node and strore the value. Below is an illustration of the topic and the python implementation of insertion.

In this, the base case is when the left/right node of the current node is None and we can fill it up, and the recursive case is when the value is less/greater than that of the current node but the corresponding child for the node is already filled up with another node, and so we travel down to that node and repeat the process.

def insert(value,node):
    if value < node.data:
        if node.left == None:
            node.left = Node(value)
        else:
            print "Going Left"
            insert(value,node.left)
    else:
        if node.right == None:
            node.right = Node(value)
        else:
            print "Going Right"
            insert(value,node.right)
    return

Search

Next up we will be talking about searching for a particular value in a BST. When we are searching for a value in a Binary Search Tree, we again have to use recursion. And with the way a Binary Search Tree is arranged, it is actually pretty efficient to search through.

Consider the following example. Below I have a tree and I want to search for the value 19 and since it is a tree I have to start from the top/root.

Since 19 is less than 27, I know that there is no way it is in the right child of the root node, because only values greater than 27 can go in the right. That means I have to search in the left, as only values greater than or equal to 27 can go there. So now we are at 14. 19 is greater than 14, so that means we look in the right. And what do you know, we have found 19. This structure, or method of finding nodes works because if the value we are trying to find is greater than the data in the current node and the right child of the node has a child (another node), than it shows us that there is some possibility that the value we are trying to look for exists, because we have not finished looking through the tree. Same logic applies to the left side. Else, if we are in a situation where the value we are looking for is greater than the data in the current node but that node does not have a right child, than we can conclude that the node does not exist. Because there is no possibility that the value we are trying to look for exists in those BOUNDS.

Hold up, wtf are bounds!? Well lets look back at the example above. When we are looking for 19, the first thing we are saying is “Ok, 19 is less than 27, and since there is a left child, it means that any numbers between -∞ and 27 MAY exist in the left subtree”. And what do you know, 19 exists in that range of numbers. Now we look at 14, and since 19 is greater than 14 and there is a right child to the node, we can say “Ok, this means that any numbers between 15 and +∞ MAY exist in this right subtree”. And finally we find 19.

If we were looking for, lets say 20 in the same tree, and we repeat the same process, we would not find it. This is because we will end up at 19, which does not have any children, and we will be saying “Ok, if there is no right child, then that means that nothing 19 and +∞ exists in this right subtree. Hence, this does not exist”. And this is absolutely right. Below is the code for searching:

def search(value, node):
    if value == node.data:
        return True
    if value < node.data and node.left == None:
        return False
    if value >= node.data and node.right == None:
        return False
    if value <> node.data and node.left == None and node.right == None:
        return
    else:
        if value < node.data:
            return search(value, node.left)
        elif value >= node.data:
            return search(value,node.right)

This method is called Binary Search, and you may have heard of this algorithm before. This is because it can already be used in a sorted array, which leads me to my third method for our BST.

Print Sorted

Since the left child of every node consists of nodes less than the current node, we can conclude that the leftmost node in a tree is the smallest node in the tree, and the rightmost node in a tree is the biggest node in the tree. But what about the nodes ‘in between’ the minimum and maximum?

If the leftmost node is the smallest node, than its root node will be the second smallest node in the tree, becasue that would be the ‘next greatest’ node in the tree. On the other side of the root node (right side), will be the third greatest value in the node. BUT REMEMBER! By leftmost/rightmost, we mean to say that the left/right child of that node is set to None . So in the tree below, the leftmost node would be 1 and the right most node would be 14:

But what does this all mean, and why is it helpful? Knowing these things allows us to print the binary tree as a sorted list. Sorted list means that all values in the list are arranged from least to greatest.

Remember how we talked about how a tree is a recursive structure, because it is made up of many subtrees? Well, this property will come in handy. To print out a sorted list, we first have to travel to the smallest node in the tree recursively. As we are travelling down recursively, we keep adding more stacks to our call stack. When we get to it, we print the data stored in the node, and then we check if the minimum node has any right children, by seeing if it is set to None or not. When we are done with checking both children, we simply ‘pop’ this stack, and move on to the next layer on the call stack.

Now we do this process for each of the ‘sub-trees’ of the node, and in the end we get list of numbers in sorted manner that are in the tree. Remember, when we solve this problem for each subtree, we are basically solving a small part of a bigger problem.

Lets do an example with the tree on the left. We start with the node 8, and we keep travelling down until we hit a node with no left child, in this case 1. We then print 1, and move up to 3, after realizing that the node 1 does not have a right child. We print out 3 , and then check if it has a right child. 3 has a right child, and so we travel to the smallest node in the right sub tree of 3, and we reach 4. 4 does not have any children, so we move back up to 6, and print 6, and this process keeps going on, until we come back to the root node at 8, and only have one layer in the call stack. We then print 8, and check if the node has a right child. And so this process starts over for the whole right side of the tree. Here is the code, and this is one of the problems in which doing out an example of this algorithm makes sense, or just looking at the code and getting it:

def printSorted(node):
    if node.left <> None:
        printSorted(node.left)
    print node.data
    if node.right <> None:
        printSorted(node.right)

This code will print out the binary tree in sorted manner, and this is known as inorder traversal. There are two other forms of traversal, known as preorder and postorder, but in my opinion inorder is the most useful because sorting something that is always useful when dealing with real-world problems.

Deleting a node

Ah, this is the one. This is the one method that really requires some thinking. When we first read the title of this section, we may think to ourselves that “Oh, lets just find the node using our search() method, and then replace it’s data with None “.Well, it’s not that simple. When we are replacing the data in the node with None , we are not deleting the actual existence of the node from memory. We are just saying that this node will store None , but the node will still exist. This can mess up a whole lot of things in the tree, and it will not preserve it’s fundamental property of the left node being less than the root node and the right node being greater than the root node. Going through all the things that can go wrong by using this method is out of the scope of this tutorial, but just remember that it is not actually deleting.

Deletion is a big topic in BST, so lets start simple. Suppose we want to delete the node 4 from the binary tree below. What we first do is we travel to the node by searching for it, and then we check if it has any children. In this case, 4 does not have any children, and therefore we can delete it without having to take care of any ‘loose strings’. We delete 4 by looking for a node that has 4 as one of it’s nodes, and then we set that child equal to None . This is the trick when dealing with deletion! We will call this process of deleting a node with no children the base case in the algorithm.

Now let’s look at the next case of the deletion. This is when the node we are trying to delete has a child node as well. This is a little bit more tricky, as we can certainly not set the data in the node equal to None , nor can we use the trick we discussed about before. We could however replace the data in that node with the node’s successor/predecessor.

A node’s successor is the node that is right after the node when we have a sorted binary tree. For example, in a list of numbers from 1–10, the successor of 1 is 2. The successor of a node is always found in it’s right subtree, and it is the smallest value in the right subtree (minimum). When we find it, we can just copy the data from the successor onto the node we want to delete. If the succesor node does not have any children, than we simply remove the node by applying the base case (we just talked about this), and we will be starting from this from the right child of the node that was supposed to be deleted at first. This will successfully delete a node from the tree, and you will also be able to print the tree out in sorted manner. If the succesor node has any children, then we will repeat this method, you guessed it, recursively on the original successor node of the node we actually want to delete. This process will keep going on until we hit the base case.

This same logic applies to the predecessor. The only difference is that the predecessor is the node right before the node we want to delete when we are printing it out in a sorted manner. We now look for this node in the left subtree of the node we want to delete, and it is the biggest node in the subtree (maximum). We then repeat the same process as for the successor node if we find a child for the predecessor node. Else, we perform the base case starting from the left node of the original node we wanted to delete.

Finally, if the node we want to delete had two children, we look for the successor of the node. We can look for the predecessor if we want, but it really does not matter, as the binary tree is still preserved. So here is the code. This one was definetly the longest one to write.

def search(value, node):
    if value == node.data:
        return True
    if value < node.data and node.left == None:
        return False
    if value >= node.data and node.right == None:
        return False
    if value <> node.data and node.left == None and node.right == None:
        return
    else:
        if value < node.data:
            return search(value, node.left)
        elif value >= node.data:
            return search(value,node.right)
def maxNode(node):
    if node.right <> None:
        return maxNode(node.right)
    if node.right == None:
        return nodedef minNode(node):
    if node.left <> None:
        return minNode(node.left)
    if node.left == None:
        return node
def deleteChildNode(value, node):
    if node.left <> None and node.left.data == value:
        node.left = None
        return "Node is deleted"
    if node.right <> None and node.right.data == value:
        node.right = None
        return "Node is deleted"
    else:
        if value < node.data:
            return deleteChildNode(value, node.left)
        elif value >= node.data:
            return deleteChildNode(value,node.right)
def deleteNode(value, node):
    if search(value, node) == False:
        return "Did not find node"
    else:
        delete = searchNode(value, node)        
        if delete.right <> None:
            minimum = minNode(delete.right)
            delete.data = minimum.data
            if minimum.left == None and minimum.right == None:
                 if delete.right.data == minimum.data:
                    delete.right = None
                    return "Node has been deleted"
                 else:
                    return deleteChildNode(minimum.data, delete.right)
            if minimum.right <> None:
                return deleteNone(minimum.right)
        if delete.left <> None and delete.right == None:
            maximum = maxNode(delete.left)
            delete.data = maximum.data
            if maximum.left == None and maximum.right == None:
                if delete.left.data == maximum.data:
                    delete.left = None
                    return "Node has been deleted"
                else:
                    return deleteChildNode(maximum.data, delete.left)
            if maximum.left <> None:
                return deleteNode(maximum.left)
        if delete.left == None and delete.right == None:
            return deleteChildNode(value, node)

And yeah, those are some of the basic operations of the binary search tree, and a pretty nifty introduction into recursion. I loved writing this tutorial, as it helped me learn so much on the way aswell, and I hope it helps you too. Before you leave though, there is just a little more code. This one just encompasses the data structure into one class which can be used to play around with.

class BinarySearchTree():
    def __init__(self, val):
        self.root = Node(val)
    def insert(self, val):
        return insert(val, self.root)
    def search(self, val):
        return search(val, self.root)
    def printSorted(self):
        return printSorted(self.root)
    def deleteNode(self, val):
        return deleteNode(val, self.root)
    def searchNode(self, val):
        return searchNode(val, self.root)
    def maxNode(self):
        return maxNode(self.root)
    def minNode(self):
        return minNode(self.root)

In my next post, we will be learning about the time complexity of the different operations in the Binary Search Tree. If you do not know what that means, I do not either, so lets learn about it together.