The function I need: return the index of the node in the tree if the key is found, return -1 otherwise.

My pseudo-code:

int search(Node node,int key){
   if(node->key==key){
      return node->index;
   }
   if(node->leftchild exists){
     search(node->leftchild,key);
   }
   if(node->middlechild exists){
     search(node->middlechild,key);
   }
   if(node->rightchild exists){
     search(node->rightchild,key);
   }
}

When I call the function I will initially pass the root:

int result = search(root,key);

The part I'm missing:

After every recursion call has been made, if the condition node->key==key was never met, return -1

What is the right way to add the part I'm missing in the function I wrote above in pseudo-code?

CodePudding user response：

First, your code does not utilize the recursive calls you make. -1 is more like a default value. I would suggest this modification of your pseudocode:

int search(Node node,int key){
   if(node->key==key){
      return node->index;
   }
   int result = -1;
   if(node->leftchild exists){
      result = max(result, search(node->leftchild,key));
   }
   if(node->middlechild exists){
     result = max(result, search(node->middlechild,key));
   }
   if(node->rightchild exists){
     result = max(result, search(node->rightchild,key));
   }
   return result;
}

Important note: this code assumes that all keys are non-negative. If this condition is true you may see that result would be only updated if the search finds the node (returning -1 would not change the result). If this condition is not true, code just gets less tidy with a lot of ifs, also they are necessary if you want to return as soon as you have found one key saving performance. This code would be:

int search(Node node,int key){
   if(node->key==key){
      return node->index;
   }
   if(node->leftchild exists){
      int result = search(node->leftchild,key);
      if (result != -1) {
         return result;
      }
   }
   if(node->middlechild exists){
      int result = search(node->middlechild,key);
      if (result != -1) {
         return result;
      }
   }
   if(node->rightchild exists){
      int result = search(node->rightchild,key);
      if (result != -1) {
         return result;
      }
   }
   return -1;
}

This code has a lot of copy-paste, but the best way to get rid of it depends on the actual programming language and constraints on the keys.