0

I need help understanding this algorithm

Design a variation of algorithm TreeSearch for performing the operation findAl(k) in an ordered dictionary implemented with a binary search tree T, and show that it runs in time O(h + s), where h is the height of T and s is the size of the collection returned.

```
Algorith TreeSearch(k,v)
if T.isExternal(v) then
return v
if k < key(v) then
return TreeSearch(k, T.left(v))
else if k > key(v) then
return TreeSearch(k, T.right(v))
return v
```

This is what I came up with:

```
Algorith TreeSearch(k,v)
if T.isExternal(v) then
return v
if hasLeft(v) and k < key(v) then
return TreeSearch(k, T.left(v))
if hasLeft(v) and k > key(v) then
return TreeSearch(k, T.right(v))
return v
```

What I understand is that the algorithm should traverse through the whole tree and return all entries with the same key.