An algorithm for searching a binary search tree follows immediately from the binary search tree property. Although the search algorithm can be cast in a recursive fashion, it’s just as easy (and more efficient) to write it iteratively. Here is a Search( ) function that shows how this is done:
Bnode *Search(Bnode *t, const TYPE &x)
// Returns pointer to a node matching the data x if
// such a node is in the tree t; otherwise, a 0 is returned
{
while (t) {
if (x == t->info) break;
t = (x < t->info) ? t->Left() : t->Right();
}
return t;
}
However, searching in binary search can be done in recursive fashion as well and hence most of the problems related to Binary Search Trees are done in recursive fashion, its worth looking into its recursive version as well:
/*
Given a binary tree, return true if a node
with the target data is found in the tree. Recurs
down the tree, chooses the left or right
branch by comparing the target to each node.
*/
static int search(struct node* node, int target) {
// 1. Base case == empty tree
// in that case, the target is not found so return false
if (node == NULL) {
return(false);
}
else {
// 2. see if found here
if (target == node->data) return(true);
else {
// 3. otherwise recur down the correct subtree
if (target < node->data) return(search(node->left, target));
else return(search(node->right, target));
}
}
}
