Consider a binary search tree where each tree node v has a field v.sum which stores the sum of all the keys in the subtree rooted at v. We wish to add an operation SumLE(K) to this binary search tree which returns the sum of all the keys in the tree whose values are less than or equal to K.

(a) Describe an algorithm, SumLE(K), which returns the sum of all the keys in the tree whose values are less than or equal to K. Give pseudo-code for your algorithm. Your algorithm should take the same time as operation TreeSearch.

procedure TreeSearch(x,K)

1 if (x = NIL) or (K = x.key) then

2 return (x);

3 else if (K < x.key) then

4 TreeSearch(x.left, K);

5 else

6 TreeSearch(x.right, K);

7 end

-------------------------

(b) Explain why your algorithm is correct, i.e., why it returns the sum of all the keys whose values are less than or equal to K.

(c) Analyze the running time of your algorithm in terms of the size n and height h of the binary search tree.