Modify the TREE-SEARCH procedure for binary search trees so that it returns the list of all objects x such that x.key = k, where k is the search key value. Provide a possibly tight asymptotic running time of your procedure.

(please write down each detail proof steps)

Hint:

TREE-SEARCH(x,k)

1 if x == NIL or k == x.key

2 return x

3 if k < x.key

4 return TREE-SEARCH(x.left, k)

5 else return TREE-SEARCH(x.right, k)

)