while-loop condition check

Question

I am trying to create a binary search tree in C.

I've figured out most parts, but one thing kept on bothering me even when I finished the task.

It was the search function, which is supposed to return with the node's data (temp->data in this case).

However, it kept on giving me errors when I wrote out the code as the following:

char bst_search(int key){

tree_pointer temp = root;

  while(temp != NULL){ 

        if(temp->key < key){ // navigate down the tree
        temp = temp->right;
        } else temp = temp->left;

        if(temp->key == key){
        return temp->data;
        }

   }    

return NULL;

}

This function failed when a key that was not within the binary tree (thus should return NULL) and kept crashing. After trying out a few possibilities, I've realized that moving the key check to the front part of the while loop solved this issue.

char bst_search(int key){

tree_pointer temp = root;

    while(temp != NULL){

      if(temp->key == key){
        return temp->data;
       }

      if(temp->key < key){ // navigate down the tree
         temp = temp->right;
       } else temp = temp->left;

    }   

return NULL;

}

I am curious when the variable within the loop condition (temp) gets modified in the body code of its' loop (as temp has been changed to temp->left or temp->right), does the condition get checked again?

I feel that I am missing out something that's pretty obvious for most of you guys. Any help is appreciated!

Answer 1

No, the while loop (and the C language in general) will not do things behind your back like re-evaluate the condition when the condition variable changes.

The statement:

    if(temp->key < key)
        temp = temp->right;
    else
        temp = temp->left;

_{(please format your code properly on stackoverflow)}

will store NULL into temp when you reach leaf nodes.

However, immediately afterwards, you do: if(temp->key == key). This will crash and burn if temp is NULL.

So, by rearranging the statements, you avoid the situation where you try to access temp->key when temp is NULL.

The standard way of doing checking and branching of this kind is as follows:

    if( temp->key < key )
        temp = temp->right;
    else if( temp->key > key )
        temp = temp->left;
    else //temp->key == key
       return temp->data;