Correcting Node Height for BST in CPP

Question

I just need some help adjusting the height variable of ndoes in a BST, I cannot find out what is wrong with the logic in my code.

void BST<T>::fix_height(Node* node){
    Node* current_node = node;
    while(current_node !=nullptr){

       if(current_node ->right != NULL && current_node ->left !=NULL){
          current_node->height = std::max(current_node->left->height, current_node->right->height) + 1;
           
       }else if(current_node ->right == nullptr){
           current_node->height = current_node->left->height+1;

       }else if(current_node ->left == nullptr){
          current_node ->height = current_node->right->height+1;

       }else{
           current_node->height = 0;
       }  
       current_node = current_node -> parent; 
       print(current_node);
    }
}

Answer 1

First of all, the code assumes that the children of the node that is passed as argument to fix_height have their heights already set correctly. If this is not guaranteed, then it already goes wrong there. But without seeing the context of the call of this function we must assume the function is only called on leaves or on nodes whose children have their height correctly set.

There is one problem inside the function: if node is a leaf, then the second if block will be entered, where an invalid reference is made to current_node->left.

One way to fix this, is to swap the first and the last case, and so first deal with the leaf case:

void BST<T>::fix_height(Node* node) {
    Node* current_node = node;
    while (current_node != nullptr) {
        if (current_node->right == nullptr && current_node->left == nullptr) {
            current_node->height = 0;
        } else if(current_node->right == nullptr) {
            current_node->height = current_node->left->height + 1;
        } else if(current_node->left == nullptr) {
            current_node->height = current_node->right->height + 1;
        } else {        
            current_node->height = std::max(current_node->left->height, current_node->right->height) + 1;
        }
        current_node = current_node->parent; 
        print(current_node);
    }
}

A minor thing: in C++ don't use NULL for null pointers. You had a mix of NULL and nullptr. Only use the latter.