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

}

}

}

### Like this:

Like Loading...

*Related*