Question

• Given the pseudocode for Binary Search Algorithm as below:

BinarySearch(A, p, r, V)

   if p < r

q = (p + r)/2

if V = A[q]

return q

else if V > A[q]

return BinarySearch(A, q+1, r, V)

   else return BinarySearch(A, p, q-1)

else if p = r,

   if V = A[p]

   return p

else

return -1

   return -1

end function

Using this pseudocode, write a function for BinarySearch and also complete the program, by writing a main, which will supply the array A (you may like to use the same main as the other programming exercise you have done so far), and also get an user input for V (which should have same data type as the array itself).

Call the function BinarySearch by sending the array, and 1 for p, N for r and V, store the value in a variable x, which stores the position number of the searched key V.

Then check if x is -1, then display data is not found, otherwise display the value of x, by using a suitable title, saying Data V is found in location x (value of x should be displayed).

Must compile, run and copy and paste the program underneath this word document.

2. a) Construct a Binary Search Tree using the following data:

54 37 17 28 44 71 64 60

b) Illustrate how will you search for 30 from the above tree and how many searches will be needed.

c) Illustrate how you will delete the root from the above tree, redraw the tree after deletion.

d) Add a new data after conducting operation c, say the new value = 50

(Do not start from scratch, show this operation by adding onto existing Tree).

e) Write down the pre-order, post-order and in-order traversal.

Answer 1

// Hope this helps you
//If u face any doubt feel free to ask in the comments 
// I will be very happy to help you

#include <bits/stdc++.h> 
using namespace std; 
// Recursive function of binary search
int binarySearch(int arr[], int l, int r, int x) //Parameter array,start index,end index,and the value to be searched
{ 
        if (r >= l) 
        { 
                int mid = l + (r - l) / 2; 
                // If the element is present at the middle itself
                if (arr[mid] == x) 
                        return mid; 

                // If element is smaller than mid, then 
                // it can only be present in left subarray 
                if (arr[mid] > x) 
                        return binarySearch(arr, l, mid - 1, x); // calling for the left subarray

                // Else the element can only be present 
                // in right subarray 
                return binarySearch(arr, mid + 1, r, x); // calling function for right subarray
        } 

        // We reach here when element is not 
        // present in array 
        return -1; // No found in the array
} 

int main() 
{ 
        int arr[] = {2,5,8,10,15,25,32,45}; 
        int V;
        cout<<"Enter the item to be searched: ";
        cin>>V;
        int n = sizeof(arr) / sizeof(arr[0]); 
        int x = binarySearch(arr, 0, n - 1, V); // return -1 if not found else return position of data
        (x == -1) ? cout << "Data is not found"
                                : cout << "Data "<<V<<" is present at index " << x; 
        return 0; 
} 

Code screenshots:

OUTPUT SCREENSHOTS:

2)

part (a) to (d) are in image

(e) Preorder traversal of the given tree in a part is:

54,37,17,28,44,71,64,60

Inorder Traversal is:

17,28,37,44,54,60,64,71

Postorder traversal is:

28,17,44,37,60,64,71,54