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:
- Python
- C++
def r_search(self, data, subtree)
bool search(const T& data, const Node* subtree) const
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.
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.
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)
- Python
- C++
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)
template <typename T>
class BST{
struct Node{
T data_;
Node* left_;
Node* right_;
Node(const T& data, Node* left=nullptr, Node* right=nullptr){
data_=data;
left_=left;
right_=right;
}
};
//single data member pointing to root of tree
Node* root_;
//recursive search() function. This function returns
//true if data is found in tree with root subtree,
//false otherwise
bool search(const T& data, const Node* subtree) const{
bool rc=false;
//if it tree is empty, the if is skipped and we return false
if(subtree != nullptr){
if(data == subtree->data_){
//base case 2: we find it in the root of subtree
rc=true;
}
else if(data < subtree->data_){
//data is smaller than that stored in root. If we find it,
//it will be in left subtree, so we call search to see if its
//there and return the result
rc=search(data,subtree->left_);
}
else{
//otherwise its bigger, use the search() function
//to see if its in right subtree and return the result
rc=search(data,subtree->right_);
}
}
return rc;
}
public:
bool search(const T& data) const{
//call and return result from recursive search() function
return search(data,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.
- Python
- C++
def insert(self, data, subtree):
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. However, we actually want to modify the pointer being passed in so we are going to pass in a reference to the pointer instead of just the pointer:
void insert(const T& data, Node*& 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.
- Python
- C++
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)
class BST{
struct Node{
T data_;
Node* left_;
Node* right_;
Node(const T& data, Node* left=nullptr, Node* right=nullptr){
data_=data;
left_=left;
right_=right;
}
};
//single data member pointing to root of tree
Node* root_;
void insert(const T& data, Node*& subtree){
//NOTE: the & after Node* is really important for this. It makes
//subtree another name for whatever you pass in. For example, if
//in the initial call from non-recursive insert(), we pass in root_
//subtree is actually another name for root_ itself. Not just a copy
//of data in the root. This means that when we change subtree, we
//are actually changing root.
if(subtree==nullptr){
//if tree is empty, make subtree point to the new node
subtree=new Node(data);
}
else if (data < subtree->data_){
//if data is smaller than data in subtree's root
//insert it to the left.
insert(data,subtree->left_);
}
else{
//otherwise its bigger so we insert it into the right subtree
insert(data,subtree->right_);
}
}
public:
...
void insert(const T& data){
insert(data,root_);
}
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.
- Python
- C++
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("")
class BST{
struct Node{
T data_;
Node* left_;
Node* right_;
Node(const T& data, Node* left=nullptr, Node* right=nullptr){
data_=data;
left_=left;
right_=right;
}
};
Node* root_;
//prints the values of the tree who's root is stored in subtree from
//smallest to biggest
void inOrderPrint(const Node* subtree) const{
//base case is we have an empty tree... in that case we do nothing
//and exit the function
if(subtree!=nullptr){
//values in left_ are smaller, we need to print them all first
inOrderPrint(subtree->left_);
//print value in current node
std::cout << subtree->data_ << std::endl;
//values in right_ are bigger, we need to print them all after we
//print current node
inOrderPrint(subtree->right_);
}
}
public:
...
void inOrderPrint() const {
inOrderPrint(root_);
}
...
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
- Python
- C++
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("")
class BST{
struct Node{
T data_;
Node* left_;
Node* right_;
Node(const T& data, Node* left=nullptr, Node* right=nullptr){
data_=data;
left_=left;
right_=right;
}
};
Node* root_;
//prints the values of the tree who's root is stored in subtree
//by printing the value in a node then the values in its left subtree
//followed by the values in the right subtree
void preOrderPrint(const Node* subtree) const{
//base case is we have an empty tree... in that case we do nothing
//and exit the function
if(subtree!=nullptr){
//print value in current node
std::cout << subtree->data_ << std::endl;
//print left subtree
preOrderPrint(subtree->left_);
//print right subtree
preOrderPrint(subtree->right_);
}
}
public:
...
void preOrderPrint() const {
preOrderPrint(root_);
}
...
Destructor
A destructor must deallocate every node in the tree. There are different ways that this could be done but the simplest is to write a post-order tree traversal. The reason its a traversal is simply because we need to visit every node in the tree and destroy it. The reason it has to be done in a post order manner is because we must first destroy both subtrees attached to a node before deleting the node or we will lose access to those subtrees.
Similar to the print functions, the destructor will be written by private recursive function that accepts a the root of the subtree we are trying to deallocate. We will call this function destroy:
void destroy(Node* subtree);
Note that because we actually don't care about changing the value of the pointers themselves we don't need a & after the Node* part. Just go through and deallocate every node
As with all the other traversals, we have a base case where if the tree is empty we do nothing. Otherwise we will simply first begin by destroying the left subtree, then the right subtree then we can deallocate the root node of the current subtree (pointed to by the argument subtree)
class BST{
struct Node{
T data_;
Node* left_;
Node* right_;
Node(const T& data, Node* left=nullptr, Node* right=nullptr){
data_=data;
left_=left;
right_=right;
}
};
Node* root_;
//prints the values of the tree who's root is stored in subtree
//by printing the value in a node then the values in its left subtree
//followed by the values in the right subtree
void destroy(Node* subtree){
//base case is we have an empty tree... in that case we do nothing
//and exit the function
if(subtree!=nullptr){
destroy(subtree->left_);
destroy(subtree->right_);
delete subtree;
}
}
public:
...
~BST(){
destroy(root_);
}
...