Chris Choi Chris Choi - 15 days ago 8
C Question

while-loop condition check

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

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;
Comments