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. This will be a Node*. It will typically involve working with the node this pointer points. The public interfaces for these recursive functions will typically start it off by passing in the root_ data member 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:

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->left_ or subtree->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)

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. 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 insert, 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{
    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.

    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

    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_);
    }
...