How to search in a Binary Search Tree?


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

Advertisements
  1. Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: