top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Give a basic algorithm for searching a binary search tree?

+3 votes
476 views
Give a basic algorithm for searching a binary search tree?
posted Apr 15, 2015 by Jalal

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

2 Answers

+1 vote
 
Best answer

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)
        printf("Not found! %d is not present in the list.\n", search);
answer Apr 15, 2015 by Arshad Khan
+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
answer Apr 16, 2015 by Mohammed Hussain
...