Assuming we store this value (e.g. x.size) write pseudocode for a function BSTKeyLessThan(T, k)that takes a tree T and a number k and returns the number of values in the tree T that are less than k. For example, if the tree had the number 1 through 9 in it, then BSTKeyLessThan(T, 5)should return 4. What is the best-case and worst-case running time of your algorithm?

If the current node is equal to the value K then return the x.size of the left node if it exists, otherwise return 0 if the current node is greater than the value K then recur to the right child Time Complexity-O(tree height)

Median) (if the node is NULL return, the number and test is = = half of the total nodes if yes, save the median otherwise, recur for the right child Time Complexity O(n)

To use the x.size property

now the problem reduces to find number of lesser of equal elements to half of number of nodes of tree

Median

traverse the tree in inorder way

get BSTKEYLESSTHAN and add one to it

check if this number is equal to the n/2

if yes, this is the median node

else continue the traversal.

Time Complexity :- O(n*height of tree)