C++ Data Structures and Algorithms

Finding out whether a key exists in a BST

Suppose we have a BST and need to find out if a key exists in the BST. It's quite easy to check whether a given key exists in a BST, since we just need to compare the given key with the current node. If the key is smaller than the current node's key, we go to the left subtree, otherwise we go to the right subtree. We will do this until we find the key or when there are no more nodes to find. The implementation of the Search() operation should be as follows:

BSTNode * BST::Search(BSTNode * node, int key){    // The given key is    // not found in BST    if (node == NULL)        return NULL;    // The given key is found    else if(node->Key == key)        return node;    // The given is greater than    // current node's key else if(node->Key ...