Iterative Methods

This section looks at the functions that are implemented iteratively (or the iterative version of the functions)

Constructor

When we create our tree, we are going to start with an empty tree. Thus, our constructor simply needs to initialize the data member to nullptr.

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_; 
public:
    BST(){
        root_=nullptr;
    }
...
};

Insert - Iterative version

This function will insert data into the tree. There are two ways to implement this function, either iteratively or recursively. We will start by looking at the iterative solution. In this situation, we begin by taking care of the empty tree situation. If the tree is empty we simply create a node and make root_ point to that only node. Otherwise, we need to go down our tree until we find the place where we must do the insertion and then create the node.

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_; 
public:
...
    void insert(const T& data){
        if(root_==nullptr){
            root_=new Node(data);
        }
        else{
            bool isInserted=false;   //set to true when once we insert the node
            Node* curr=root_;        //used to iterate through nodes
            while(!isInserted){
                if(data < curr->data_){
                    //data belongs in left subtree because it is 
                    //smaller than current node
                    if(curr->left_){
                        //there is a node to the left so go left
                        curr=curr->left_;
                    }
                    else{
                        //there isn't a node to left
                        //create a node to the left
                        curr->left_=new Node(data);
                        isInserted=true;
                    }
                }
                else{
                    //data belongs in right subtree.
                    if(curr->right_){
                        //there is a node to the right so go right
                        curr=curr->right_;
                    }
                    else{
                        //there isn't a node to right
                        //create a node to the right
                        curr->right_=new Node(data);
                        isInserted=true;
                    }
                }
            }
        }
    }
...
};

Search - Iterative version

The key operation that is supported by a binary search tree is search. For our purposes we will simply look at finding out whether or not a value is in the tree or not. The search operation should never look at the entire tree. The whole point of the binary search tree is to make this operation fast. We should search it so that we can eliminate a portion of the tree with every search operation.

To do this we start at the root and compare that node's data against what we want. If it matches, we have found it. If not, we go either left or right depending on how data relates to the current node. If at any point we have an empty tree (ie the pointer we are using for iterating through the tree becomes nullptr) we stop the search and return false. If we find a node that matches we stop and return true.

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_; 
public:
    bool search(const T& data) const {
        Node* curr=root_;    //used  to iterate through tree        
        bool found=false;    //true if we find it false if we haven't yet

        //loop until we either find it or we have no more tree
        while(!found && curr){ 
            if(data==curr->data_){
                found=true;
            }
            else if(data < curr->data_){
                curr=curr->left_;
            }
            else{
                curr=curr->right_;
            }
        }
        return  found;
    }
};

Breadth First Print

Writing a breadth-first traversal involves using the queue data structure to order what nodes to deal with next. You want to deal with the nodes from top to bottom left to right, and thus you use the queue to order the nodes. Here is an example of how we will do this.

We begin by declaring a queue (initially empty)

Initial Empty Queue

Prime the Queue

We start prime the queue by putting the root into the queue. In this example, we always check to ensure no nullptrs are ever added to the queue. Alternatively we allow the addition of nullptrs and decide how to deal with them when we dequeue.

Prime the queue

Dequeue front of node and process it by adding its non-nullptr children into the queue, print the node

remove front node (20) and add 20's left and right children to queue, print 20

Continue by dequeuing front node and processing it in same manner

remove front node (10) and add 10's left and right children to queue, print 10

Repeat again as 25 only has a right child only it is added

Repeat again as 25 only has a right child only it is added

Repeat once again with 5 which has no children thus nothing is added to queue

Repeat once again with 5 which has no children thus nothing is added to queue

Repeat again with 15 (also no children)

Repeat again with 15 (also no children)

Repeat with 35 and add its children

Continue by removing 30

And one more time with 40

At this point queue is empty and thus, we have completed our breadthfirst print of the tree.

In code form, this is how we will write our code (we assume we have a template queue available:

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_; 
public:
...
    void breadthFirstPrint() const{
        Queue<Node*> theNodes;  //we assume the queue class has these functions
                                //enqueue(), dequeue(), front(), isEmpty()
        //prime queue
        if(root_){
            theNodes.enqueue(root_);
        }
        //while we have nodes to deal with
        while(!theNodes.isEmpty()){
            //deal with first node and remove it from queue
            Node* curr=theNodes.front();
            theNodes.dequeue();
            if(curr->left_){
                //if the current node has a left child add it to queue
                theNodes.enqueue(curr->left_);
            }
            if(curr->right_){
                //if the current node has a right child add it to queue
                theNodes.enqueue(curr->right_);
            }
            //print the current node's data
            std::cout << curr->data_ << " ";
        }
        std::cout << std::endl;
    }
...

};