Determine if there is a node in a binary postorder anti-sorted tree with key $k$

Question

A binary postorder anti-sorted tree is a binary tree for which the post-order traversal gives the keys that are saved at the nodes of the tree in descending order. Present a pseudocode for the most effective algorithm that you can think of that will find if there is a node in a binary postorder anti-sorted tree with key $k$. Which is the asymptotically most exact bound for the time execution of the above algorithm in the worst case?

I thought that the tree will be of the following form. Am I right?

I wrote the following algorithm, that returns 1 if there is a node with key k and 0 if there isn't such a node.

Alg(int k, pointer R){
   if (R==NULL) return 0;
   if (R->key==k) return 1;
   else if (R->key<k){
        if (R->lc!=NULL){
           if (k>R->lc->key){
               if (R->rc!=NULL)  return Alg(k,R->rc);
           }
           else return Alg(k,R->lc);
         }
         else if (R->rc!=NULL) return Alg(k,R->rc);
   } 
   else return 0;

  }

Could you tell me if my idea is right?

Answer 1

Firstly, the diagram you drew is a valid example of such a tree.

Secondly, the problem statement says "pseudocode;" everyone has a different understanding of what this means. I'd ask your instructor about how particular s/he is if this is for a class. Since I'm not too familiar with C++, your pseudocode is a bit too code-like for me (but that's personal preference, not something that's right/wrong).

I'll convert your pseudocode to even more abstract pseudocode, so we're not worrying with pointers, etc:

Alg(Tree T, key):
  if (T is empty):  return "not found"

  Node currNode = T.root
  if (currNode.value = key): 
    return "found"

  else if (currNode.value < key):
    if (currNode.hasLeftChild):
      if (currNode.leftChild.value < key):
        if (currNode.hasRightChild): // (1)
          return Alg(currNode.rightSubtree, key)
        else: 
          return Alg(currNode.leftSubtree, key) // (2)

    else if (currNode.hasRightChild):
      return Alg(currNode.rightSubtree, key)

  else:
    return "not found"

I'm a bit confused on why you have the if/else constructs that you do between the lines that I've marked $(1)$ and $(2)$ above. It seems like you're doing some unnecessary checking. However, your algorithm looks as if it will return the right answer even so.

It seems to me that the a better way to decide which path to take is to check "is the key less than or equal to the value at my left node? If yes, follow the left branch. If no, follow my right branch."

That is, my pseudocode would be:

Alg(Tree T, key):
  if (T is empty):  return "not found"

  Node currNode = T.root
  if (currNode.value = key): 
    return "found"

  else if (currNode.value < key):
    if (currNode.isLeaf):
      return "not found" //no children

    if (currNode.hasLeftChild AND key <= currNode.leftChild.value):
      //key is in the first half of the list
      return Alg(currNode.leftSubtree, key) 

    else if (currNode.hasRightChild):
      //key must be in the second half of the list, or absent.
      return Alg(currNode.rightSubtree, key) 

  else:
    return "not found"

As to asymptotic performance: the worst case is that the node is not there, and you must traverse the entire height of the tree. Thus, the algorithm operates in time proportional to $\mathcal O (\lg n)$, where $n$ is the number of nodes in the tree.