Give an efficient algorithm to find all keys in a min heap that are smaller than a provided value X. The provided value does not have to be a key in the min heap. Evaluate the time complexity of your algorithm

The algorithm to this question as follows:

Algorithm:

finding_small_element (element, Key xa) / /defining method that accepts parameter

{

if (element. value> = xa) / /check value

{

//skiping node

return;

}

print (element. value); //print value

if (element. left! = NULL) / /check left node value

{

finding_small_element (element. left, xa); / /using method

}

if (element. right! = NULL) / /check right node value

{

finding_small_element (element. right, xa); / /using method

}

}

Explanation:

In the above pre-order traversing algorithm a method "finding_small_element" is defined, that accepts two parameter, that is "element and ax', in which "element" is node value and ax is its "key".

Inside this if block is used that check element variable value is greater then equal to 0. In the next step, two if block is defined, that check element left and the right value is not equal to null, if both conditions are true, it will check its right and left value. In this algorithm, there is no extra need for traversing items.