# Give a basic algorithm for searching a binary search tree?

148 views
Give a basic algorithm for searching a binary search tree?
posted Apr 15, 2015

+1 vote

For binary search tree your set of number should be in order i.e ascending or descending.

For example:

``````Assume you have as set of integer as (1, 2, 3, 5, 19, 44, 45, 55, 58) and  you need to find 55.
So for searching, you have to do the followings:
start = points it to the beginning of the number set. i.e "1"
end = points it to the last element of the set ie. "58"
middle = number of elemet / 2 i.e 4th elemet (19)
``````

Now you need to check there in a loop. Till your number i.e (55) matched with the "middle"

``````  while (first <= last) {
if (array[middle] == search) {
printf("%d found at location %d.\n", search, middle+1);
break;
} else if (array[middle]  <  search) {
// number is lies in between middle and last so update the first index
first = middle + 1;
} else {
// number is lies in between middle and first so update the last index
last = middle - 1;
}
middle = (first + last) / 2;  //update the middle index
}
if (first > last)
``````
+1 vote
``````1. if the tree is empty, then the target is not in the tree, end search

2. if the tree is not empty, the target is in the tree

3. check if the target is in the root item

4. if target is not in the root item, check if target is smaller than the root’s value

5. if target is smaller than the root’s value, search the left subtree

6. else, search the right subtree
``````