Question

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.

Answer 1

(a)
procedure SumLE(x,K)

if (x = NIL) or (K = x.key) then
   rightSum = 0
   if x.right = NIL
       rightSum = 0
   else
       rightSum = (x.right).sum + (x.right).key
   return x.sum - rightSum + x.key
else if (K < x.key) then
   SumLE(x.left,K);
else
   SumLE(x.right,K);
end

(b) In a Binary Search Tree, all the keys in the right sub tree are greater than the root and left sub tree are less than the root. So for SumLE we need sum of all the keys in its left subtree. That is exactly what we achieved.

(c) This takes same time as Searching in a tree. The time taken will be O(logn), where n is the number of nodes in the tree.