TreeSearch BST

[cgen]

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.

[Taywin]

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

Not sure that is a correct assumption. It does not traverse through the whole tree but only the branch of the tree it should go.

OK, what is isExternal() method? Is "v" a tree node? I know that "k" is the search element.

Anyway, go back to the algorithm. I do not see the "collection" or "s" you are talking about in the problem. What I see here is a regular binary tree search. You are traversing the tree to check for which node the element "k" is and return it if found or "external" (what is this external thing?). Anyway, the "h" in the big O means that you may compare only once up to the height number of the tree. So the comparison will never be more than the height of a binary tree - O(h).

Now my guess for "s" is the size of children of a node. In this case, it will always be 2 because it is either left or right. So each time you go through a height, you may or may not compare both children. Therefore, the time complexity of the algorithm is O(h+s).

[cgen]

isExternal method checks if it is null. I can replace T.isExternal(v) with 'if v ==null '

I looked through the code and took your advice.
This is what I came up with. I am assuming that duplicates are inserted on the right:

if v == null return null //the key is not found
if k = key(v)
  print v.value
  return TreeSearch(k, T.Right(v))  //keeps checking on the right
if k != key(v)
   if k < key(v) and hasLeft
     return Treesearch(k, T.left(v)
   else if k > key and hasRight
     return TreeSearch(k, T.hasRight(v)

[Taywin]

I see... If the isExternal() represent "null" then you do NOT need "hasLeft" or "hasRight" because the recursion will take care of the null value.

The insertion accepts the duplicate and places it in the right child branch. If you want a print out only, then it is fine to do what you are doing now. The method will always returns null regardless. But it would be better to do as follows...

// Algorithm TreeSearch(k,v)
// v is a node in the tree
if v == null return null // base case to stop recursion
if k < v.key()
  return Treesearch(k, v.left())
else  // same as k >= v.key()
  print v.value
  return TreeSearch(k, v.right())

If you want a node returned if found (or null if not), then you must not check for equal but return the first node found. The person who uses your method must remove the first found node from the tree before he or she can get to the next duplicated node.

//Algorithm TreeSearch(k,v)
// v is a node in the tree
if v == null return null //the key is not found
if k < v.key()
  return Treesearch(k, v.left())
else if k > v.key()
  return TreeSearch(k, v.right())
return v  // not null, less than, or greater, it is found

You could also change the insertion to ignore duplicated too, so there would be no duplicated value in your binary tree.

The time complexity of the method won't be changed because of binary tree characteristics.

PS: I changed your key(v) and T.left(v) to v.key() and v.left() because these methods should be member of the class, not static.

[cgen]

if v == null return null //the key is not found
if k < v.key()
  return Treesearch(k, v.left())
else if k > v.key()
  return TreeSearch(k, v.right())
return v

So will this code run in o(h+s) time, since it is returning the node v after each recursion?

[Taywin]

Yes. It will traverse the tree at most "h" time to find a matched node. The "h" is the height of the tree. The "s" is the size of children of a node.

[cgen]

Thanks a lot :)