how to implement a pseudocode for a search algorithm for BST

Question

I've studied a bit about recursion and I implemented what I learned on a binary search tree. I have a successful search and an unsuccessful search as my base case, and the algorithm function takes two parameters as input - one is the key that we are searching for in the binary search tree, and the other is the node that we are propagating the search from. The problem lies on formulating a pseudocode that answers the question.

I did the following approach - some said that it's wrong as I don't need the "@return" statement when I did the recursive call on either a node's left or right child but I argued that this is correct as we are expecting something out of that recursive function call and that if we remove the "@return" statement it will remove the recursive stack trace to the original caller of that function that begins the recursion and that node calling the search_bst(k, v) function will not have anything to return.

function search_bst(k, v):
   if v.isExternal():
      return v
   if k = key(v):
      return v
   # search the left sub-tree
   else if k < key(v):
      return search(k, v.left)
   # search the right sub-tree
   else k > key(v):
      return search(k, v.right)

Answer 1

You are absolutely right that the return is needed for the reasons you have given.

Here are some comments on the code you presented:

• The method isExternal is not intuitive to me. It could be interpreted to mean isLeaf, or it could mean that your tree is defined with explicit NIL objects that have this method and only in that case return true. The latter interpretation would be a bit odd, as in real object oriented languages, null represents the absence of an object/pointer, and so you wouldn't have a method to call.

• If isExternal means isLeaf, then this algorithm would not work when the BST is empty (has no nodes). And secondly, it would then be wrong to return v, as that would return a node that does not have the desired key.

• The final case (k > key(v)) should not have to be tested, as it is the only other possibility left.

I would therefore rewrite the code like this:

function search_bst(k, v):
   if isNull(v) or k = key(v):
      return v
   else if k < key(v):
      # search the left sub-tree
      return search(k, v.left)
   else:
      # search the right sub-tree
      return search(k, v.right)