Skip to main content

Recursive Methods

One of the way to look at a binary search tree is to define the tree recursively. A binary search tree is either empty or consists of a root node who has two children each of which is a binary search tree. This recursive nature makes certain functions easy to write recursively. This portion of the implementation will look at how to write member functions recursively.

For all recursive functions involving a binary search tree, you typically need at least one argument that gives you access to the root of a subtree. The public interfaces for these recursive functions will typically start it off by passing in the root as the first argument.

When writing these functions, we look at the problem in terms of the subtree. Often the base case will involve dealing with an empty subtree (or doing nothing with an empty subtree). This section of the notes will deal with some details about how this can be accomplished and some typical ways of dealing with recursive solutions.

search - recursive function

This is the same function as the iterative version of the search (does the same thing). Only difference is that it is written recursively.

As stated earlier, recursive functions for our trees typically involve looking at it in terms of what to do with a tree (defined as root of the tree).

For the recursive search() function, we will need to write a recursive function and call it from the public search() function. The recursive function will not only have data for the argument but also the root of the subtree where we will be trying to find the data. Note that we cannot use the data member root because we will lose the tree if we do. We must actually pass in the argument so that it can change in each call without causing the root to be modified. Thus, our recursive function has the following prototype:

def r_search(self, data, subtree)

The above function returns true if data is in the tree who's root is pointed to by subtree, false otherwise.

As with all recursive cases we always want to start by figuring out the base case of the recursive function

Under what circumstances would it be so easy to find the answer we can confidently return the result immediately? So, given a tree (where all we see is the address of the root node) what situations would allow us to know that we have a result.

In our case there are two base cases:

  • the tree is empty. If the tree is empty, the value can't be in the tree, so we can return false immediately.
  • the tree is not empty but the value we want is in the root of the tree. If that is the case we don't need to look at the rest of the tree. We already know that its there.
caution

a tree being empty is usually a base case for recursive functions involving a binary search tree. If this is not a base case you are considering, you should ask why and what would happen if you got an empty tree and whether or not you have made a mistake.

So... what if its not a base case? Well if its not a base case, then we know the following:

  • there is a tree with at least a root node
  • the data isn't in the root node

Thus if the value exists, its either in the left subtree or the right subtree of the root. As the BST places data so that values in right subtree is bigger than value in current node and value in left is smaller, which subtree we look at depends on how the data compares against the root. If the data is smaller than value in root, then it could only be in left subtree if it there at all. Similarly if it is bigger, it could only be in right subtree. Therefore to find if value is in tree we simply make the recursive call to search() using either subtree's left or subtree's right.

info

For any function that involves looking for a value in the tree it is never more correct to look at both left and right. The difference will be O(log n) vs O(n)

class BST:
class Node:
# Node's init function
def __init__(self, data=None, left=None, right=None):
self.data = data
self.left = left
self.right = right

# BST's init function
def __init__(self):
self.root = None

def r_search(self, data, subtree):
if subtree is None:
return None
else:
if data < subtree.data:
return self.r_search(data, subtree.left)
elif data > subtree.data:
return self.r_search(data, subtree.right)
else:
return subtree

def search_recursive(self, data):
return self.r_search(data, self.root)

Insert - recursive version

Similar to search, we must write a separate private recursive insert() function that is called from the public insert function. Similar to search(), the recursive insert function also requires a pointer to the node we are trying to insert the data into. We think about this as inserting data into subtree. In python, there isn't really a pass by reference concept. As such, we will need to utilize the return statement in order to correctly attach our new tree.

def insert(self, data, subtree):

As with search, we want to start by figuring the base and recursive cases. For the base case, if the tree was empty we will simply make the current node the root of the tree. If not, we will want to insert the value either into the left or right subtree depending on how it compares to the data in the root of the subtree.

class BST:
class Node:
# Node's init function
def __init__(self,data=None,left=None,right=None):
self.data = data
self.left = left
self.right = right

#BST's init function
def __init__(self):
self.root = None

def ins(self, data, subtree):
if(subtree==None):
return BST.Node(data)
elif(data < subtree.data):
subtree.left = self.ins(data,subtree.left)
return subtree
else:
subtree.right = self.ins(data, subtree.right)
return subtree

def recursive_insert(self,data):
self.root = self.ins(data,self.root)
info

There are other solutions where you would check if left/right child is nullptr and then simply make the new node if it is instead of doing the recursive call. Doing it that way requires an extra check to ensure root itself isn't null in the original insert function. Its takes a bit more work to ensure the code works for all cases.

InOrder Print function

To print all values in the tree from smallest to biggest, we can write the function recursively. This is an example of an inorder tree traversal. That is we will visit every node in the tree exactly one time and process it exactly one time.

This function is most easily written recursively. As with all other recursive function for bst we will pass in the root of the subtree. This function will be called from the public inOrder print() function.

The base case for this function is simply that of an empty tree. If the tree is empty, there is nothing to print so we do nothing and exit function.

if tree isn't empty we want to start by printing all values smaller than the current node (stored in left subtree), then the current node then all the values bigger than the current node (stored in right subtree). if its a tree, we'll use the inOrderPrint() function to print those so that they will be printed in order also.

class BST:
class Node:
# Node's init function
def __init__(self,data=None,left=None,right=None):
self.data = data
self.left = left
self.right = right

#BST's init function
def __init__(self):
self.root = None


def print_inorder(self, subtree):
if(subtree != None):
self.print_inorder(subtree.left)
print(subtree.data, end = " ")
self.print_inorder(subtree.right)

def print(self):
self.print_inorder(self.root)
print("")
info

In this solution notice we don't check the pointers before we make the function calls for recursive functions... the first thing we do when we enter the function is ensure the pointer isn't nullptr so there is no need to do a check before hand. This method has the advantage that it doesn't create a special case for empty trees (ie root_==nullptr). root_ is handled the same as any other other Node pointer.

Pre Order Print

The pre-order print function is similar to the inorder print function except that we print the current node before printing its subtrees. This is the ordering that would be used if we were to do something like listing the contents of a file system.

The code for this is pretty much identical to inOrderPrint(). The only difference is in when we print the current node. What we want to do is print the current node, then its left and right subtrees

class BST:
class Node:
# Node's init function
def __init__(self,data=None,left=None,right=None):
self.data = data
self.left = left
self.right = right

#BST's init function
def __init__(self):
self.root = None


def print_preorder(self, subtree):
if(subtree != None):
print(subtree.data, end = " ")
self.print_preorder(subtree.left)
self.print_preorder(subtree.right)

def print(self):
self.print_preorder(self.root)
print("")