Search Algorithms in C++ || Binary Search Tree || Part 2

This is the second post in continuation of the last post on Binary Search Trees in C++.

Just like we did for vectors, linked strings; we will have a struct for Node to represent nodes of the tree. The node will contain a  data element, a pointer to the left child and a pointer to the right child.

template <class T>
struct node{
             T data;
             node * lChild, rChild;
}

And then a class for BST (Binary Search Tree). In the private members, we will have a node* root element that will serve as the beginning of tree traversal. We will have some basic functions like insert, search and remove in the class. I have made an iterator for the traversal in my class. Given below is the code:

template <class T>
class bst {
private:
struct Node {
T data;
Node* lchild;
Node* rchild;

};   //I've made the struct inside the class so that user cannot access it

Node* root;   //private members
int s;

Node* createNode(const T & obj )  //a utility function
{
Node* temp = new Node;
temp->data = obj;
temp->lchild = temp->rchild = nullptr;
return temp;

}

int height(Node* n )  //to get tree height at a specific node

{

if (n == nullptr)

{

return 0;

}

else

{

int ln = height(n->lchild);     //used recursion to get tree height using

                                                                    originating branches from the child

int rn = height(n->rchild);

return (max(rn, ln) + 1);

}

}

bst()  //default constructor

{

s = 0;

root = nullptr;

}

Strategy used in Insert:  We have two nodes to help in our traversal, Previous and Current. In the parameter we take 'key', which is the data to be inserted, we compare that data with the current node and go to its left if the data in the current node is greater than the key (as the left child is smaller than its parent) and go to its right if the data in the current node is smaller than the key (as the right child is greater than its parent).

  >> Note: The data here is template T type which can be an int, string or any custom datatype. The comparison is done using < and > operators which may be type specific. E.g. different for integer comparison and different for string comparsion. 

Also, in every traversal we update Previous pointer with the Current pointer to move to the next and update Current with left or right child's pointer using comparison. The while loop traversal keeps going till we reach the leaf position where we can insert our new node. After the while loop ends, the Previous pointer is pointing to the node of which we will make a new child, either left or right, after comparison of the data.

If the previous pointer is simply empty, it means no node has been created so far and the tree is empty, so we create a new node at the Root. 

void insert(const T & key)

{

                

Node* curr = root;  //current element in the traversal, in the beginning it is root

Node* prev = nullptr;    //previous element, i.e. parent of the current node

while (curr != nullptr)    //if the tree is not empty, start traversal

{

prev = curr;

if (curr->data > key)   //if key < current then go to left

{

curr = curr->lchild;  

}

else if (curr->data < key)    //if key > current then go to right

{

curr = curr->rchild;

}

else

return;    //no repetition allowed

}

if (prev == nullptr)

{

root = createNode(key);    //if empty

s++;

}

else        //tree size >= 1

{

if (prev->data < key)     //key is bigger

{

prev->rchild = createNode(key);

s++;

}

else if (prev->data > key)    //key is smaller

{

prev->lchild = createNode(key);

s++;

}

}

}

bool search(const T & key)  //returns the true if the key found in the tree, else false
{
Node* curr = root;
while (curr != nullptr && curr->data != key )
{
if (curr->data > key)
curr = curr->lchild;   //key is smaller
else
curr = curr->rchild;   //key is greater
}

if (curr != nullptr)
return true;

return false;

}

int size()
{
return s;
}

int height()
{
return height(root);
}

Here is the code for the Iterator of this class, it will be in the public section of the BST class

//************* ITERATOR **************//

class iterator {
private:
vector <Node*> nodes;
int index;

public:
iterator(int i, vector <Node*> & v)
{
nodes = v;    //automatically does deep copy in vector class
index = i;
}

iterator(const iterator & obj)
{
nodes = obj.nodes;
index = obj.index;
}

bool operator != (const iterator & obj)
{
if (index != obj.index)
return true;

return false;
}

void  operator ++ ()
{
index++;

}

void operator ++ (int ind)
{
index = index + ind;
}

T operator * ()
{
return nodes[index]->data;
}
};


/****************** End of Iterator Class *********************/

We will also require some utility functions in the BST class to help initialise the iterator.

==> To see what are iterators and how they work, Click Here!

void getNodes_inOrder(Node* n, vector  <Node*> & v )
{
if (n != nullptr)
{
getNodes_inOrder(n->lchild, v);
v.push_back(n);
getNodes_inOrder(n->rchild, v);
}
}

iterator begin()
{
vector <Node*>  v;
getNodes_inOrder(root, v);
iterator itr(0, v);     //starting index is 0
return itr;
}

iterator end()
{
vector <Node*>  v;
getNodes_inOrder(root, v);
iterator itr(v.size(), v);     //ending index is vector's size
return itr;
}

The Remove function of this class is a bit tricky and long in code length. So I will explain that in the next post. Complete code will be posted in the next post.

Thank you for reading and comment below if you have any questions! :)